Fault diameter of Cartesian product graphs

The (k−1)-fault diameter Dk(G) of a k-connected graph G is the maximum diameter of G−F for any F⊂V(G) with |F|<k. Krishnamoorthy and Krishnamurthy first proposed this concept and gave Dκ(G₁)+κ(G₂)(G₁×G₂)?Dκ(G₁)(G₁)+Dκ(G₂)(G₂) when κ(G₁×G₂)=κ(G₁)+κ(G₂), where κ(G) is the connectivity of G. This paper gives a counterexample to this bound and establishes Dk₁+k₂(G₁×G₂)?Dk₁(G₁)+Dk₂(G₂)+1 for any ki-connected graph Gi and ki?1 for i=1,2.     

The diameter of Hanoi graphs

Many questions regarding the Tower of Hanoi problem have been posed and answered during the years. Variants of the classical puzzle, such as allowing more than 3 pegs, and imposing limitations on the possible moves among the pegs, raised the analogous questions for those variants. One such question is: given a variant, and a certain number of disks, find a pair of disk arrangements such that the minimal number of moves required for changing from the first to the second is maximal over all pairs. One of the main results of the paper is identifying these for the Cyclic_h variants—the variants with h pegs arranged along a uni-directional circle—to be the pairs of perfect configurations where the destination peg is right before the source peg.     

Edge-fault-tolerant pancyclicity and bipancyclicity of Cartesian product graphs with faulty edges

Let r≥ 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to $2\lfloor \frac{n(G)}{2}\rfloor$, where $n(G)$ is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to $n(G)$, where $r\ge 3$. A graph is k-edge-fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k-edge-fault r-bipancyclic and k-edge-fault r-pancyclic can be defined similarly. Given two graphs G and H, where $n(G)$, $n(H)\ge$ 9, let $k_1$, $k_2\ge 5$ be the minimum degrees of G and H, respectively. This study determined the edge-fault r-bipancyclic and edge-fault r-pancyclic of Cartesian product graph $G\times H$ with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of ${\mathit{NQ}}_{m_r,\dots ,m_1}$ and ${\mathit{GQ}}_{m_r,\dots ,m_1}$.     

On the diameter of geometric path graphs of points in convex position

For a set S of n points in convex position in the plane, let P(S) denote the set of all plane spanning paths of S. The geometric path graph of S, denoted by Gn, is the graph with P(S) as its vertex set and two vertices P,Q∈P(S) are adjacent if and only if P and Q can be transformed to each other by means of a single edge replacement. Recently, Akl et al. [S.G. Akl, K. Islam, H. Meijer, On planar path transformation, Inform. Process. Lett. 104 (2007) 59-64] showed that the diameter of Gn is at most 2n−5. In this note, we derive the exact diameter of Gn for n?3.     

On Clark and Suen bound-type results for k-domination and Roman domination of Cartesian product graphs

A set S of vertices of a graph G is a dominating set for G if every vertex of G is adjacent to at least one vertex of S. The domination number γ(G), of G, is the minimum cardinality of a dominating set in G. Moreover, if the maximum degree of G is Δ, then for every positive integer k≤Δ, the set S is a k-dominating set in G if every vertex outside of S is adjacent to at least k vertices of S. The k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a k-dominating set in G. A map f: V→<texlscub>0, 1, 2</texlscub>is a Roman dominating function for G if for every vertex v with f(v)=0, there exists a vertex u∈N(v) such that f(u)=2. The weight of a Roman dominating function is f(V)=∑ _u∈V f(u). The Roman domination number γ_R(G), of G, is the minimum weight of a Roman dominating function on G. In this paper, we obtain that for any two graphs G and H, the k-domination number of the Cartesian product of G and H is bounded below by γ(G)γ _k (H)/2. Also, we obtain that the domination number of Cartesian product of G and H is bounded below by γ(G)γ_R(H)/3.     

Local colourings of Cartesian product graphs

A local colouring of a graph G is a function c: V(G)→? such that for each S ? V(G), 2≤|S|≤3, there exist u, v∈S with |c(u)?c(v)| at least the number of edges in the subgraph induced by S. The maximum colour assigned by c is the value χ_?(c) of c, and the local chromatic number of G is χ_?(G)=min {χ_?(c): c is a local colouring of G}. In this note the local chromatic number is determined for Cartesian products G □ H, where G and GH are 3-colourable graphs. This result in part corrects an error from Omoomi and Pourmiri [On the local colourings of graphs, Ars Combin. 86 (2008), pp. 147–159]. It is also proved that if G and H are graphs such that χ(G)≤? χ_?(H)/2 ?, then χ_?(G □ H)≤χ_?(H)+1.     

Cyclic bundle Hamiltonicity

Cyclic bundle Hamiltonicity cbH(G) of a graph G is the minimal n for which there is an automorphism α of G such that the graph bundle C _n □^α G is Hamiltonian. We define an invariant I that is related to the maximal vertex degree of spanning trees suitably involving the symmetries of G and prove cbH(G)≤I≤cbH(G)+1 for any non-trivial connected graph G.     

Fast algorithms for the dominating set problem on permutation graphs

AnO(n log logn) (resp.O(n² log² n)) algorithm is presented to solve the minimum cardinality (resp. weight) dominating set problem on permutation graphs, assuming the input is a permutation. The best-known previous algorithm was given by FÄrber and Keil, where they use dynamic programming to get anO(n² (resp.O(n³)) algorithm. Our improvement is based on the following three factors: (1) an observation on the order among the intermediate terms in the dynamic programming, (2) a new construction formula for the intermediate terms, and (3) efficient data structures for manipulating these terms.This research was supported in part by the National Science Foundation under Grant CCR-8905415 to Northwestern University.     

网络拓扑的超能整循环图构造

循环图是一类重要的网络拓扑结构图,在并行计算和分布计算中发挥重要作用。图[G]的能量[E(G)]定义为图的特征值的绝对值之和。具有[n]个顶点的图[G]称为超能图如果图[G]的能量[E(G)>2n-2]。一个图称为循环图,若它是循环群上的Cayley图,即它的邻接矩阵是一个循环矩阵;整循环图是指循环图的特征值全为整数。借助Ramanujans和,利用Euler函数和Mobius函数,讨论了整循环图的超能性。利用Cartesian积图给出了一个构造超能整循环图的方法。     

Honeycomb toroidal graphs are Cayley graphs

There is a particular family of trivalent vertex-transitive graphs that have been called generalized honeycomb tori by some and brick products by others. They have been studied as hexagonal embeddings on the torus as well. We show that all these graphs are Cayley graphs on generalized dihedral groups.     

Strong orientations of complete k-partite graphs achieving the strong diameter

In this paper, we consider each integer d between the lower and upper orientable strong diameter of the complete k-partite graph K(m₁,m₂,…,mk), and show that there does exist a strong orientation of K(m₁,m₂,…,mk) such that sdiam(K)=d.     

The differential of the strong product graphs

Let G=(V, E) be a graph of order n and let B(D) be the set of vertices in V ? D that have a neighbour in the set D. The differential of a set D is defined as ? (D)=|B(D)|?|D| and the differential of a graph to equal the maximum value of ?(D) for any subset D of V. In this paper we obtain several tight bounds for the differential of strong product graphs. In particular, we investigate the relationship between the differential of this type of product graphs and various parameters in the factors of the product.     

Function-described graphs for modelling objects represented by sets of attributed graphs

We present in this article the model function-described graph (FDG), which is a type of compact representation of a set of attributed graphs (AGs) that borrow from random graphs the capability of probabilistic modelling of structural and attribute information. We define the FDGs, their features and two distance measures between AGs (unclassified patterns) and FDGs (models or classes) and we also explain an efficient matching algorithm. Two applications of FDGs are presented: in the former, FDGs are used for modelling and matching 3D-objects described by multiple views, whereas in the latter, they are used for representing and recognising human faces, described also by several views.     

Approximation and inapproximability results for maximum clique of disc graphs in high dimensions

We prove algorithmic and hardness results for the problem of finding the largest set of a fixed diameter in the Euclidean space. In particular, we prove that if A^∗ is the largest subset of diameter r of n points in the Euclidean space, then for every ε>0 there exists a polynomial time algorithm that outputs a set B of size at least |A^∗| and of diameter at most . On the hardness side, roughly speaking, we show that unless P=NP for every ε>0 it is not possible to guarantee the diameter for B even if the algorithm is allowed to output a set of size .     

The Cayley network of expanded Pancake graphs

Signed permutation group has important applications in genome rearrangement as well as the construction of networks. In this paper, we propose a new interconnection network named extended Pancake graph, we investigate its topological properties, and give a routing algorithm with the diameter upper bounded by 2n?1. Some embedding properties are also derived. In conclusion, we present a comparison of some familiar networks with the Cayley graph EP _n .     

Note on the connectivity of line graphs

Let G be a connected graph with vertex set V(G), edge set E(G), vertex-connectivity κ(G) and edge-connectivity λ(G).A subset S of E(G) is called a restricted edge-cut if G−S is disconnected and each component contains at least two vertices. The restricted edge-connectivity λ₂(G) is the minimum cardinality over all restricted edge-cuts. Clearly λ₂(G)?λ(G)?κ(G).In 1969, Chartrand and Stewart have shown that

     

Conditional fault diameter of crossed cubes

The conditional connectivity and the conditional fault diameter of a crossed cube are studied in this work. The conditional connectivity is the connectivity of an interconnection network with conditional faults, where each node has at least one fault-free neighbor. Based on this requirement, the conditional connectivity of a crossed cube is shown to be 2n−2$2n-2$. Extending this result, the conditional fault diameter of a crossed cube is also shown to be D(C_Qn)+3$D\left(C{Q}_n\right)+3$ as a set of 2n−3$2n-3$ node failures. This indicates that the conditional fault diameter of a crossed cube is increased by three compared to the fault-free diameter of a crossed cube. The conditional fault diameter of a crossed cube is approximately half that of the hypercube. In this respect, the crossed cube is superior to the hypercube.     

Reconstruction of interval graphs

The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related to it, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems by limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. Since the number of interval graphs that can be obtained from an interval graph by adding a vertex and edges incident to it can be exponentially large, developing polynomial time algorithms for LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs.