Bandwidth of the strong product of two connected graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)-f(y)|:xy∈E(G)} taken over all proper numberings f of G. The strong product of two graphs G and H, written as G(S_P)H, is the graph with vertex set V(G)×V(H) and with (u₁,v₁) adjacent to (u₂,v₂) if one of the following holds: (a) u₁ and v₁ are adjacent to u₂ and v₂ in G and H, respectively, (b) u₁ is adjacent to u₂ in G and v₁=v₂, or (c) u₁=u₂ and v₁ is adjacent to v₂ in H. In this paper, we investigate the bandwidth of the strong product of two connected graphs. Let G be a connected graph. We denote the diameter of G by D(G). Let d be a positive integer and let x,y be two vertices of G. Let denote the set of vertices v so that the distance between x and v in G is at most d. We define δ_d(G) as the minimum value of over all vertices x of G. Let denote the set of vertices z such that the distance between x and z in G is at most d-1 and z is adjacent to y. We denote the larger of and by . We define η(G)=1 if G is complete and η(G) as the minimum of over all pair of vertices x,y of G otherwise. Let G and H be two connected graphs. Among other results, we prove that if δ_D(H)(G)?B(G)D(H)+1 and B(H)=⌈(|V(H)|+η(H)-2)/D(H)⌉, then B(G(S_P)H)=B(G)|V(H)|+B(H). Moreover, we show that this result determines the bandwidth of the strong product of some classes of graphs. Furthermore, we study the bandwidth of the strong product of power of paths with complete bipartite graphs.     

Bandwidth of the composition of two graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)−f(y)| : xyE(G)} taken over all proper numberings f of G. The composition of two graphs G and H, written as G[H], is the graph with vertex set V(G)×V(H) and with (u₁,v₁) is adjacent to (u₂,v₂) if either u₁ is adjacent to u₂ in G or u₁=u₂ and v₁ is adjacent to v₂ in H. In this paper, we investigate the bandwidth of the composition of two graphs. Let G be a connected graph. We denote the diameter of G by D(G). For two distinct vertices x,yV(G), we define w_G(x,y) as the maximum number of internally vertex-disjoint (x,y)-paths whose lengths are the distance between x and y. We define w(G) as the minimum of w_G(x,y) over all pairs of vertices x,y of G with the distance between x and y is equal to D(G). Let G be a non-complete connected graph and let H be any graph. Among other results, we prove that if |V(G)|=B(G)D(G)−w(G)+2, then B(G[H])=(B(G)+1)|V(H)|−1. Moreover, we show that this result determines the bandwidth of the composition of some classes of graphs composed with any graph.     

On the diameter of Kronecker graphs

We prove that a.a.s. as soon as a Kronecker graph becomes connected it has a finite diameter.     

Reconstruction of distance hereditary 2-connected graphs

A graph is reconstructible if it is determined up to isomorphism from the collection of all its one-vertex deleted unlabelled subgraphs. It is shown that all distance hereditary 2-connected graphs $G$ such that $\text{diam}\left(G\right)=2$ or $\text{diam}\left(G\right)=\text{diam}\left(\overline{G}\right)=3$ are reconstructible.     

On the connectivity and superconnected graphs with small diameter

In this paper, first we prove that any graph G is 2-connected if diam(G)≤g−1 for even girth g, and for odd girth g and maximum degree Δ≤2δ−1 where δ is the minimum degree. Moreover, we prove that any graph G of diameter diam(G)≤g−2 satisfies that (i) G is 5-connected for even girth g and Δ≤2δ−5, and (ii) G is super-κ for odd girth g and Δ≤3δ/2−1.     

Superconnectivity of regular graphs with small diameter

A graph is superconnected, for short super-κ, if all minimum vertex-cuts consist of the vertices adjacent with one vertex. In this paper we prove for any r-regular graph of diameter D and odd girth g that if D≤g−2, then the graph is super-κ when g≥5 and a complete graph otherwise.     

Diameter-girth sufficient conditions for optimal extraconnectivity in graphs

For a connected graph G, the rth extraconnectivity κ_r(G) is defined as the minimum cardinality of a cutset X such that all remaining components after the deletion of the vertices of X have at least r+1 vertices. The standard connectivity and superconnectivity correspond to κ₀(G) and κ₁(G), respectively. The minimum r-tree degree of G, denoted by ξ_r(G), is the minimum cardinality of N(T) taken over all trees T⊆G of order |V(T)|=r+1, N(T) being the set of vertices not in T that are neighbors of some vertex of T. When r=1, any such considered tree is just an edge of G. Then, ξ₁(G) is equal to the so-called minimum edge-degree of G, defined as ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, where d(u) stands for the degree of vertex u. A graph G is said to be optimally r-extraconnected, for short κ_r-optimal, if κ_r(G)?ξ_r(G). In this paper, we present some sufficient conditions that guarantee κ_r(G)?ξ_r(G) for r?2. These results improve some previous related ones, and can be seen as a complement of some others which were obtained by the authors for r=1.     

On total domination vertex critical graphs of high connectivity

A graph is called γ-critical if the removal of any vertex from the graph decreases the domination number, while a graph with no isolated vertex is γ_t-critical if the removal of any vertex that is not adjacent to a vertex of degree 1 decreases the total domination number. A γ_t-critical graph that has total domination number k, is called k-γ_t-critical. In this paper, we introduce a class of k-γ_t-critical graphs of high connectivity for each integer k≥3. In particular, we provide a partial answer to the question “Which graphs are γ-critical and γ_t-critical or one but not the other?” posed in a recent work [W. Goddard, T.W. Haynes, M.A. Henning, L.C. van der Merwe, The diameter of total domination vertex critical graphs, Discrete Math. 286 (2004) 255-261].     

On the corona of two graphs

Aequationes mathematicae -     

Hamilton-connected indices of graphs

Let G be an undirected graph that is neither a path nor a cycle. Clark and Wormald [L.H. Clark, N.C. Wormald, Hamiltonian-like indices of graphs, ARS Combinatoria 15 (1983) 131-148] defined hc(G) to be the least integer m such that the iterated line graph L^m(G) is Hamilton-connected. Let be the diameter of G and k be the length of a longest path whose internal vertices, if any, have degree 2 in G. In this paper, we show that . We also show that κ³(G)≤hc(G)≤κ³(G)+2 where κ³(G) is the least integer m such that L^m(G) is 3-connected. Finally we prove that hc(G)≤|V(G)|−Δ(G)+1. These bounds are all sharp.     

Diameter and connectivity of 3-arc graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v,u,x,y) of vertices such that both (v,u,x) and (u,x,y) are paths of length two. The 3-arc graph of a given graph G, X(G), is defined to have vertices the arcs of G. Two arcs uv,xy are adjacent in X(G) if and only if (v,u,x,y) is a 3-arc of G. This notion was introduced in recent studies of arc-transitive graphs. In this paper we study diameter and connectivity of 3-arc graphs. In particular, we obtain sharp bounds for the diameter and connectivity of X(G) in terms of the corresponding invariant of G.     

The signless Laplacian spectra of the corona and edge corona of two graphs

We give complete information about the signless Laplacian spectrum of the corona of a graph G ₁ and a regular graph G ₂, and complete information about the signless Laplacian spectrum of the edge corona of a connected regular graph G ₁ and a regular graph G ₂.     

Total domination in planar graphs of diameter two

MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213–229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. Henning, Domination in planar graphs with small diameter, J. Graph Theory 40 (2002) 1–25] showed that there is a unique planar graph of diameter two with domination number three. It follows that the total domination number of a planar graph of diameter two is at most three. In this paper, we consider the problem of characterizing planar graphs with diameter two and total domination number three. We say that a graph satisfies the domination-cycle property if there is some minimum dominating set of the graph not contained in any induced 5-cycle. We characterize the planar graphs with diameter two and total domination number three that satisfy the domination-cycle property and show that there are exactly thirty-four such planar graphs.     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

Long cycles and paths in distance graphs

For n∈N and D⊆N, the distance graph has vertex set {0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant c_D such that the greatest common divisor of the integers in D is 1 if and only if for every n, has a component of order at least n−c_D if and only if for every n≥c_D+3, has a cycle of order at least n−c_D. Furthermore, we discuss some consequences and variants of this result.