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.     

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.     

The competition number of a graph and the dimension of its hole space

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. Recently, the relationship between the competition number and the number of holes of a graph has been studied. A hole of a graph is a cycle of length at least 4 as an induced subgraph. In this paper, we conjecture that the dimension of the hole space of a graph is not smaller than the competition number of the graph. We verify this conjecture for various kinds of graphs and show that our conjectured inequality is indeed an equality for connected triangle-free graphs.     

A Generalization of Opsut’s Lower Bounds for the Competition Number of a Graph

The notion of a competition graph was introduced by Cohen in 1968. The competition graph C(D) of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. In 1978, Roberts defined the competition number k(G) of a graph G as the minimum number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. In 1982, Opsut gave two lower bounds for the competition number of a graph. In this paper, we give a generalization of these two lower bounds for the competition number of a graph.     

Bounding the diameter of a distance-transitive graph

A graph Γ is distance-transitive if for all vertices u, v, x, y such that d(u, v) = d(x, y) there is an automorphism h of Γ such that uh = x, vh = y. We show how to find a bound for the diameter of a bipartite distance-transitive graph given a bound for the order |G_α| of the stabilizer of a vertex.     

Subpancyclicity of line graphs and degree sums along paths

A graph is called subpancyclic if it contains a cycle of length ? for each ? between 3 and the circumference of the graph. We show that if G is a connected graph on n?146 vertices such that d(u)+d(v)+d(x)+d(y)>(n+10/2) for all four vertices u,v,x,y of any path P=uvxy in G, then the line graph L(G) is subpancyclic, unless G is isomorphic to an exceptional graph. Moreover, we show that this result is best possible, even under the assumption that L(G) is hamiltonian. This improves earlier sufficient conditions by a multiplicative factor rather than an additive constant.     

Isometric cycles,cutsets, and crowning of bridged graphs

A graph G is bridged if every cycle C of length at least 4 has vertices x,y such that d_G(x,y) < d_C(x,y). A cycle C is isometric if d_G(x,y) = d_C(x,y) for all x,y ∈ V(C). We show that every graph contractible to a graph with girth g has an isometric cycle of length at least g. We use this to show that every minimal cutset S in a bridged graph G induces a connected subgraph. We introduce a “crowning” construction to enlarge bridged graphs. We use this to construct examples showing that for every connected simple graph H with girth at least 6 (including trees), there exists a bridged graph G such that G has a unique minimum cutset S and that G[S] = H. This provides counterexamples to Hahn's conjecture that d_G(u,v) ≤ 2 when u and v lie in a minimum cutset in a bridged graph G. We also study the convexity of cutsets in bridged graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 161–170, 2003     

The competition number of a graph whose holes do not overlap much

Let D be an acyclic digraph. The competition graph of D is a graph which has the same vertex set as D and has an edge between u and v if and only if there exists a vertex x in D such that (u,x) and (v,x) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices.A hole of a graph is an induced cycle of length at least four. Kim (2005) [8] conjectured that the competition number of a graph with h holes is at most h+1. Recently, Li and Chang (2009) [11] showed that the conjecture is true when the holes are independent. In this paper, we show that the conjecture is true though the holes are not independent but mutually edge-disjoint.     

Graphs with small boundary

For a pair of vertices x and y in a graph G, we denote by d_G(x,y) the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and d_G(y,v)?d_G(y,x) for each neighbor v of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by B(G).In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, |B(G)|?2 for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of |B(G)|.     

Induced path transit function, monotone and Peano axioms

The induced path transit function J(u,v) in a graph consists of the set of all vertices lying on any induced path between the vertices u and v. A transit function J satisfies monotone axiom if x,y∈J(u,v) implies J(x,y)⊆J(u,v). A transit function J is said to satisfy the Peano axiom if, for any u,v,w∈V,x∈J(v,w), y∈J(u,x), there is a z∈J(u,v) such that y∈J(w,z). These two axioms are equivalent for the induced path transit function of a graph. Planar graphs for which the induced path transit function satisfies the monotone axiom are characterized by forbidden induced subgraphs.     

On CCE graphs of doubly partial orders

Let D be a digraph. The competition-common enemy graph (CCE graph) of D has the same set of vertices as D and an edge between vertices u and v if and only if there are vertices w and x in D such that (w,u), (w,v), (u,x), and (v,x) are arcs of D. We call a graph a CCE graph if it is the CCE graph of some digraph. In this paper, we show that if the CCE graph of a doubly partial order does not contain C₄ as an induced subgraph, it is an interval graph. We also show that any interval graph together with enough isolated vertices is the CCE graph of some doubly partial order.     

Distance-hereditary graphs and signpost systems

An ordered pair (U,R) is called a signpost system if U is a finite nonempty set, R⊆U×U×U, and the following axioms hold for all u,v,w∈U: (1) if (u,v,w)∈R, then (v,u,u)∈R; (2) if (u,v,w)∈R, then (v,u,w)∉R; (3) if u≠v, then there exists t∈U such that (u,t,v)∈R. (If F is a (finite) connected graph with vertex set U and distance function d, then U together with the set of all ordered triples (u,v,w) of vertices in F such that d(u,v)=1 and d(v,w)=d(u,w)−1 is an example of a signpost system). If (U,R) is a signpost system and G is a graph, then G is called the underlying graph of (U,R) if V(G)=U and xy∈E(G) if and only if (x,y,y)∈R (for all x,y∈U). It is possible to say that a signpost system shows a way how to travel in its underlying graph. The following result is proved: Let (U,R) be a signpost system and let G denote the underlying graph of (U,R). Then G is connected and every induced path in G is a geodesic in G if and only if (U,R) satisfies axioms (4)-(8) stated in this paper; note that axioms (4)-(8)-similarly as axioms (1)-(3)-can be formulated in the language of the first-order logic.     

A characterization of block graphs

A block graph is a graph whose blocks are cliques. For each edge e=uv of a graph G, let N_e(u) denote the set of all vertices in G which are closer to u than v. In this paper we prove that a graph G is a block graph if and only if it satisfies two conditions: (a) The shortest path between any two vertices of G is unique; and (b) For each edge e=uv∈E(G), if x∈N_e(u) and y∈N_e(v), then, and only then, the shortest path between x and y contains the edge e. This confirms a conjecture of Dobrynin and Gutman [A.A. Dobrynin, I. Gutman, On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math., Beograd. 56 (1994) 18-22].     

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.     

A note on the weakly convex and convex domination numbers of a torus

The distanced_G(u,v) between two vertices u and v in a connected graph G is the length of the shortest (u,v) path in G. A (u,v) path of length d_G(u,v) is called a (u,v)-geodesic. A set X⊆V is called weakly convex in G if for every two vertices a,b∈X, exists an (a,b)-geodesic, all of whose vertices belong to X. A set X is convex in G if for all a,b∈X all vertices from every (a,b)-geodesic belong to X. The weakly convex domination number of a graph G is the minimum cardinality of a weakly convex dominating set of G, while the convex domination number of a graph G is the minimum cardinality of a convex dominating set of G. In this paper we consider weakly convex and convex domination numbers of tori.     

Degree sum and nowhere-zero 3-flows

Let G be a simple graph on n vertices. In this paper, we prove that if G satisfies the condition that d(x)+d(y)≥n for each xy∈E(G), then G has no nowhere-zero 3-flow if and only if G is either one of the five graphs on at most 6 vertices or one of a very special class of graphs on at least 6 vertices.     

Unoriented Laplacian maximizing graphs are degree maximal

A connected graph is said to be unoriented Laplacian maximizing if the spectral radius of its unoriented Laplacian matrix attains the maximum among all connected graphs with the same number of vertices and the same number of edges. A graph is said to be threshold (maximal) if its degree sequence is not majorized by the degree sequence of any other graph (and, in addition, the graph is connected). It is proved that an unoriented Laplacian maximizing graph is maximal and also that there are precisely two unoriented Laplacian maximizing graphs of a given order and with nullity 3. Our treatment depends on the following known characterization: a graph G is threshold (maximal) if and only if for every pair of vertices u,v of G, the sets N(u)?{v},N(v)?{u}, where N(u) denotes the neighbor set of u in G, are comparable with respect to the inclusion relation (and, in addition, the graph is connected). A conjecture about graphs that maximize the unoriented Laplacian matrix among all graphs with the same number of vertices and the same number of edges is also posed.     

Geodeticity of the contour of chordal graphs

A vertex v is a boundary vertex of a connected graph G if there exists a vertex u such that no neighbor of v is further away from u than v. Moreover, if no vertex in the whole graph V(G) is further away from u than v, then v is called an eccentric vertex of G. A vertex v belongs to the contour of G if no neighbor of v has an eccentricity greater than the eccentricity of v. Furthermore, if no vertex in the whole graph V(G) has an eccentricity greater than the eccentricity of v, then v is called a peripheral vertex of G. This paper is devoted to study these kinds of vertices for the family of chordal graphs. Our main contributions are, firstly, obtaining a realization theorem involving the cardinalities of the periphery, the contour, the eccentric subgraph and the boundary, and secondly, proving both that the contour of every chordal graph is geodetic and that this statement is not true for every perfect graph.     

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.     

Geodesic-pancyclic graphs

A shortest path connecting two vertices u and v is called a u-v geodesic. The distance between u and v in a graph G, denoted by d_G(u,v), is the number of edges in a u-v geodesic. A graph G with n vertices is panconnected if, for each pair of vertices u,v∈V(G) and for each integer k with d_G(u,v)?k?n-1, there is a path of length k in G that connects u and v. A graph G with n vertices is geodesic-pancyclic if, for each pair of vertices u,v∈V(G), every u-v geodesic lies on every cycle of length k satisfying max{2d_G(u,v),3}?k?n. In this paper, we study sufficient conditions of geodesic-pancyclic graphs. In particular, we show that most of the known sufficient conditions of panconnected graphs can be applied to geodesic-pancyclic graphs.