A study 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 graph G is defined to have the arcs of G as vertices such that two arcs uv,xy are adjacent if and only if (v,u,x,y) is a 3-arc of G. In this paper, we study the independence, domination and chromatic numbers of 3-arc graphs and obtain sharp lower and upper bounds for them. We introduce a new notion of arc-coloring of a graph in studying vertex-colorings of 3-arc graphs.     

A new sufficient condition for Hamiltonian graphs

The study of Hamiltonian graphs began with Dirac’s classic result in 1952. This was followed by that of Ore in 1960. In 1984 Fan generalized both these results with the following result: If G is a 2-connected graph of order n and max{d(u),d(v)}≥n/2 for each pair of vertices u and v with distance d(u,v)=2, then G is Hamiltonian. In 1991 Faudree–Gould–Jacobson–Lesnick proved that if G is a 2-connected graph and |N(u)∪N(v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is Hamiltonian. This paper generalizes the above results when G is 3-connected. We show that if G is a 3-connected graph of order n and max{|N(x)∪N(y)|+d(u),|N(w)∪N(z)|+d(v)}≥n for every choice of vertices x,y,u,w,z,v such that d(x,y)=d(y,u)=d(w,z)=d(z,v)=d(u,v)=2 and where x,y and u are three distinct vertices and w,z and v are also three distinct vertices (and possibly |{x,y}∩{w,z}| is 1 or 2), then G is Hamiltonian.     

Spectra of Extended Double Cover Graphs

The construction of the extended double cover was introduced by N. Alon [1] in 1986. For a simple graph G with vertex set V = {v ₁, v ₂, ..., v _n }, the extended double cover of G, denoted G ^*, is the bipartite graph with bipartition (X, Y) where X = {x ₁, x ₂, ..., x _n } and Y = {y ₁, y ₂, ..., y _n }, in which x _i and y _j are adjacent iff i = j or v _i and v _j are adjacent in G.In this paper we obtain formulas for the characteristic polynomial and the spectrum of G ^* in terms of the corresponding information of G. Three formulas are derived for the number of spanning trees in G ^* for a connected regular graph G. We show that while the extended double covers of cospectral graphs are cospectral, the converse does not hold. Some results on the spectra of the nth iterared double cover are also presented.     

Hamiltonicity 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 graph G is defined to have vertices the arcs of G such that two arcs uv, xy are adjacent if and only if (v, u, x, y) is a 3-arc of G. We prove that any connected 3-arc graph is hamiltonian, and all iterative 3-arc graphs of any connected graph of minimum degree at least three are hamiltonian. As a corollary we obtain that any vertex-transitive graph which is isomorphic to the 3-arc graph of a connected arc-transitive graph of degree at least three must be hamiltonian. This confirms the conjecture, for this family of vertex-transitive graphs, that all vertex-transitive graphs with finitely many exceptions are hamiltonian. We also prove that if a graph with at least four vertices is Hamilton-connected, then so are its iterative 3-arc graphs.     

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.     

On the Existence of a Long Path Between Specified Vertices in a 2-Connected Graph

 Let G be a 2-connected graph with maximum degree Δ (G)≥d, and let x and y be distinct vertices of G. Let W be a subset of V(G)−{x, y} with cardinality at most d−1. Suppose that max{d _G(u), d _G(v)}≥d for every pair of vertices u and v in V(G)−({x, y}∪W) with d _G(u,v)=2. Then x and y are connected by a path of length at least d−|W|. Received: February 5, 1998 Revised: April 13, 1998     

On the adjacent-vertex-strongly-distinguishing total coloring of graphs

For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G.     

Super-connectivity and super-edge-connectivity for some interconnection networks

Let G=(V,E) be a k-regular graph with connectivity κ and edge connectivity λ. G is maximum connected if κ=k, and G is maximum edge connected if λ=k. Moreover, G is super-connected if it is a complete graph, or it is maximum connected and every minimum vertex cut is {x|(v,x)E} for some vertex vV; and G is super-edge-connected if it is maximum edge connected and every minimum edge disconnecting set is {(v,x)|(v,x)E} for some vertex vV. In this paper, we present three schemes for constructing graphs that are super-connected and super-edge-connected. Applying these construction schemes, we can easily discuss the super-connected property and the super-edge-connected property of hypercubes, twisted cubes, crossed cubes, möbius cubes, split-stars, and recursive circulant graphs.     

Computation of Topological Indices of Some Graphs

Let G=(V,E) be a simple connected graph with vertex set V and edge set E. The Wiener index of G is defined by W(G)=∑_{x,y}⊆V d(x,y), where d(x,y) is the length of the shortest path from x to y. The Szeged index of G is defined by Sz(G)=∑ _e=uv∈E n _u (e|G)n _v (e|G), where n _u (e|G) (resp. n _v (e|G)) is the number of vertices of G closer to u (resp. v) than v (resp. u). The Padmakar–Ivan index of G is defined by PI(G)=∑ _e=uv∈E [n _eu (e|G)+n _ev (e|G)], where n _eu (e|G) (resp. n _ev (e|G)) is the number of edges of G closer to u (resp. v) than v (resp. u). In this paper we find the above indices for various graphs using the group of automorphisms of G. This is an efficient method of finding these indices especially when the automorphism group of G has a few orbits on V or E. We also find the Wiener indices of a few graphs which frequently arise in mathematical chemistry using inductive methods.     

On the adjacent vertex-distinguishing acyclic edge coloring of some graphs

A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v, where uv ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by x′ _Aa (G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring of some graphs and put forward some conjectures.     

The eavesdropping number of a graph

Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v, a minimum {u, v}-separating set is a smallest set of edges in G whose removal disconnects u and v. The edge connectivity of G, denoted λ(G), is defined to be the minimum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. We introduce and investigate the eavesdropping number, denoted ε(G), which is defined to be the maximum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. Results are presented for regular graphs and maximally locally connected graphs, as well as for a number of common families of graphs.     

Cohen-macaulay bipartite graphs

Let G be a graph on the vertex set V={x ₁, ..., x _n}. Let k be a field and let R be the polynomial ring k[x ₁, ..., x _n]. The graph ideal I(G), associated to G, is the ideal of R generated by the set of square-free monomials x _ix_j so that x _i, is adjacent to x _j. The graph G is Cohen-Macaulay over k if R/I(G) is a Cohen-Macaulay ring. Let G be a Cohen-Macaulay bipartite graph. The main result of this paper shows that G{v} is Cohen-Macaulay for some vertex v in G. Then as a consequence it is shown that the Reisner-Stanley simplicial complex of I(G) is shellable. An example of N. Terai is presented showing these results fail for Cohen-Macaulay non bipartite graphs. Partially supported by COFAA-IPN, CONACyT and SNI, México.     

Lollipop graphs are extremal for commute times

Consider a simple random walk on a connected graph G=(V, E). Let C(u, v) be the expected time taken for the walk starting at vertex u to reach vertex v and then go back to u again, i.e., the commute time for u and v, and let C(G)=max_{u, v∈V}C(u, v). Further, let 𝒢(n, m) be the family of connected graphs on n vertices with m edges, , and let 𝒢(n)=∪_m𝒢(n, m) be the family of all connected n‐vertex graphs. It is proved that if G∈(n, m) is such that C(G)=max_{H∈𝒢(n, m)}C(H) then G is either a lollipop graph or a so‐called double‐handled lollipop graph. It is further shown, using this result, that if C(G)=max_H∈𝒢(n)C(H) then G is the full lollipop graph or a full double‐handled lollipop graph with [(2n−1)/3] vertices in the clique unless n≤9 in which case G is the n‐path. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 131–142, 2000     

The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius

Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ? V{x\in V}. In the conditional covering problem, a vertex x ? V{x \in V} covers a vertex y ? V{y \in V} (x ≠ y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C í V{C\subseteq V} so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform coverage radius in O(n ²) time, when G is an interval graph containing n vertices.     

Degree-Light-Free Graphs and Hamiltonian Cycles

 Let G and H be graphs. G is said to be degree-light H-free if G is either H-free or, for every induced subgraph K of G with K≅H, and every {u,v}⊆K, d i s t _K (u,v)=2 implies max {d(u),d(v)}≥|V(G)|/2. In this paper, we will show that every 2-connected graph with either degree-light {K _1,3, P ₆}-free or degree-light {K _1,3, Z}-free is hamiltonian (with three exceptional graphs), where P ₆ is a path of order 6 and Z is obtained from P ₆ by adding an edge between the first and the third vertex of P ₆ (see Figure 1). Received: December 9, 1998?Final version received: July 21, 1999     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

Even graphs

A nontrivial connected graph G is called even if for each vertex v of G there is a unique vertex v such that d(v, v ) = diam G. Special classes of even graphs are defined and compared to each other. In particular, an even graph G is called symmetric if d(u, v) + d(u, v ) = diam G for all u, v ∈ V(G). Several properties of even and symmetric even graphs are stated. For an even graph of order n and diameter d other than an even cycle it is shown that n ≥ 3d – 1 and conjectured that n ≥ 4d – 4. This conjecture is proved for symmetric even graphs and it is shown that for each pair of integers n, d with n even, d ≥ 2 and n ≥ 4d – 4 there exists an even graph of order n and diameter d. Several ways of constructing new even graphs from known ones are presented.     

Domination Graphs with Nontrivial Components

 A tournament is an oriented complete graph. Vertices x and y dominate a tournament T if for all vertices z≠x,y, either (x,z) or (y,z) are arcs in T (possibly both). The domination graph of a tournament T is the graph on the vertex set of T containing edge {x,y} if and only if x and y dominate T. In this paper we determine which graphs containing no isolated vertices are domination graphs of tournaments. Received: May 20, 1998 Final version received: May 26, 1999     

The rank-width of the square grid

Rank-width is a graph width parameter introduced by Oum and Seymour. It is known that a class of graphs has bounded rank-width if, and only if, it has bounded clique-width, and that the rank-width of G is less than or equal to its branch-width.The n×nsquare grid, denoted by G_n,n, is a graph on the vertex set {1,2,…,n}×{1,2,…,n}, where a vertex (x,y) is connected by an edge to a vertex (x^′,y^′) if and only if |x−x^′|+|y−y^′|=1.We prove that the rank-width of G_n,n is equal to n−1, thus solving an open problem of Oum.     

Variations of Y-dominating functions on graphs

Let Y be a subset of real numbers. A Y-dominating function of a graph G=(V,E) is a function f:V→Y such that for all vertices v∈V, where N_G[v]={v}∪{u|(u,v)∈E}. Let for any subset S of V and let f(V) be the weight of f. The Y-domination problem is to find a Y-dominating function of minimum weight for a graph G=(V,E). In this paper, we study the variations of Y-domination such as {k}-domination, k-tuple domination, signed domination, and minus domination for some classes of graphs. We give formulas to compute the {k}-domination, k-tuple domination, signed domination, and minus domination numbers of paths, cycles, n-fans, n-wheels, n-pans, and n-suns. Besides, we present a unified approach to these four problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. This paper also gives complexity results for the problems on doubly chordal graphs, dually chordal graphs, bipartite planar graphs, chordal bipartite graphs, and planar graphs.