Super-Connectivity and Hyper-Connectivity of Vertex Transitive Bipartite Graphs

A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. In this note, we proved that a vertex transitive bipartite graph is not super-connected if and only if it is isomorphic to the lexicographic product of a cycle C_n(n ≥ 6) by a null graph N_m. We also characterized non-hyper-connected vertex transitive bipartite graphs.     

Is every cycle basis fundamental?

A collection of (simple) cycles in a graph is called fundamental if they form a basis for the cycle space and if they can be ordered such that C_j(C₁ U … U C_j-1) ≠ Ø for all j. We characterize by excluded minors those graphs for which every cycle basis is fundamental. We also give a constructive characterization that leads to a (polynomial) algorithm for recognizing these graphs. In addition, this algorithm can be used to determine if a graph has a cycle basis that covers every edge two or more times. An equivalent dual characterization for the cutset space is also given.     

Cycle‐minors and subdivisions of wheels

In this paper we prove two results. The first is an extension of a result of Dirac which says that any set of n vertices of an n‐connected graph lies in a cycle. We prove that if V′ is a set of at most 2n vertices in an n‐connected graph G, then G has, as a minor, a cycle using all of the vertices of V′. The second result says that if G is an n+1‐connected graph with maximum vertex degree Δ then G contains a subgraph that is a subdivision of W_2n if and only if Δ≥2n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 100–108, 2009     

Almost claw-free graphs

We say that G is almost claw-free if the vertices that are centers of induced claws (K_1,3) in G are independent and their neighborhoods are 2-dominated. Clearly, every claw-free graph is almost claw-free. It is shown that (i) every even connected almost claw-free graph has a perfect matching and (ii) every nontrivial locally connected K_1,4-free almost claw-free graph is fully cycle extendable.     

Symmetric Hamilton cycle decompositions of complete graphs minus a 1‐factor

Let n≥2 be an integer. The complete graph K_n with a 1‐factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K_n−F has a decomposition into Hamilton cycles which are symmetric with respect to the 1‐factor F if and only if n≡2, 4 mod 8. We also show that the complete bipartite graph K_{n, n} has a symmetric Hamilton cycle decomposition if and only if n is even, and that if F is a 1‐factor of K_{n, n}, then K_{n, n}−F has a symmetric Hamilton cycle decomposition if and only if n is odd. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:1‐15, 2010     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

On brittle graphs

Chvátal defined a graph G to be brittle if each induced subgraph F of G contains a vertex that is not a midpoint of any P₄ or not an endpoint of any P₄. Every brittle graph is perfectly orderable. In this paper, we prove that a graph is brittle whenever it is HHD-free (containing no chordless cycle with at least five vertices, no cycle on six vertices with a long chord, and no complement of the chordless path on five vertices). We also design an O(n₄) algorithm to recognize HHD-free graphs, and also an O(n₄) algorithm to construct a perfect order of an HHD-free graph. It follows from this result that an optimal coloring and a largest clique of an HHD-free graph can be found in O(n₄) time.     

Closure Concepts: A Survey

In this paper we survey results of the following type (known as closure results). Let P be a graph property, and let C(u,v) be a condition on two nonadjacent vertices u and v of a graph G. Then G+uv has property P if and only if G has property P. The first and now well-known result of this type was established by Bondy and Chvátal in a paper published in 1976: If u and v are two nonadjacent vertices with degree sum n in a graph G on n vertices, then G+uv is hamiltonian if and only if G is hamiltonian. Based on this result, they defined the n-closure cl_n (G) of a graph G on n vertices as the graph obtained from G by recursively joining pairs of nonadjacent vertices with degree sum n until no such pair remains. They showed that cl_n(G) is well-defined, and that G is hamiltonian if and only if cl_n(G) is hamiltonian. Moreover, they showed that cl_n(G) can be obtained by a polynomial algorithm, and that a Hamilton cycle in cl_n(G) can be transformed into a Hamilton cycle of G by a polynomial algorithm. As a consequence, for any graph G with cl_n(G)=K _n (and n≥3), a Hamilton cycle can be found in polynomial time, whereas this problem is NP-hard for general graphs. All classic sufficient degree conditions for hamiltonicity imply a complete n-closure, so the closure result yields a common generalization as well as an easy proof for these conditions. In their first paper on closures, Bondy and Chvátal gave similar closure results based on degree sum conditions for nonadjacent vertices for other graph properties. Inspired by their first results, many authors developed other closure concepts for a variety of graph properties, or used closure techniques as a tool for obtaining deeper sufficiency results with respect to these properties. Our aim is to survey this progress on closures made in the past (more than) twenty years. Revised: September 27, 1999     

Distance-transitive dihedrants

The main result of this article is a classification of distance-transitive Cayley graphs on dihedral groups. We show that a Cayley graph X on a dihedral group is distance-transitive if and only if X is isomorphic to one of the following graphs: the complete graph K _2n ; a complete multipartite graph K _t×m with t anticliques of size m, where t m is even; the complete bipartite graph without 1-factor K _n,n − nK ₂; the cycle C _2n ; the incidence or the non-incidence graph of the projective geometry PG _d-1(d,q), d ≥ 2; the incidence or the non-incidence graph of a symmetric design on 11 vertices.     

An Upper Bound on the Basis Number of the Powers of the Complete Graphs

The basis number of a graph G is defined by Schmeichel to be the least integer h such that G has an h-fold basis for its cycle space. MacLane showed that a graph is planar if and only if its basis number is . Schmeichel proved that the basis number of the complete graph K _n is at most 3>. We generalize the result of Schmeichel by showing that the basis number of the d-th power of K _n is at most 2d+1.     

Minor and minimum cycle bases of a 3-connected planar graph

In this paper, we prove that if any set of ｜E（G）｜- ｜V（G）｜ ＋ 1 facial cycles of a 3-connected planar graph G embedded in the plane doesn＇t form a minimum cycle base of G, then any minimum cycle base of G contains a separating cycle, and G has a minor isomorphic to T6, where T6 is the graph obtained from the complete graph K6 by deleting a path with four edges.     

Intrinsically knotted graphs

In 1983, Conway and Gordon [J Graph Theory 7 ( 1 ), 445–453] showed that every (tame) spatial embedding of K₇, the complete graph on 7 vertices, contains a knotted cycle. In this paper, we adapt the methods of Conway and Gordon to show that K_3,3,1,1 contains a knotted cycle in every spatial embedding. In the process, we establish that if a graph satisfies a certain linking condition for every spatial embedding, then the graph must have a knotted cycle in every spatial embedding. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 178–187, 2002; DOI 10.1002/jgt.10017     

Edge disjoint cycles in graphs

Ore proved in 1960 that if G is a graph of order n and the sum of the degrees of any pair of nonadjacent vertices is at least n, then G has a hamiltonian cycle. In 1986, Li Hao and Zhu Yongjin showed that if n ? 20 and the minimum degree δ is at least 5, then the graph G above contains at least two edge disjoint hamiltonian cycles. The result of this paper is that if n ? 2δ², then for any 3 ? l₁ ? l₂ ? ? ? l_k ? n, 1 = k = [(δ - 1)/2], such graph has K edge disjoint cycles with lengths l₁, l₂…l_k, respectively. In particular, when l₁ = l₂ = ? = l_k = n and k = [(δ - 1)/2], the graph contains [(δ - 1)/2] edge disjoint hamiltonian cycles.     

On a Class of P5-Free Graphs

A graph G is perfect in the sense of Berge if for every induced subgraph G′ of G, the chromatic number χ(G′) equals the largest number ω(G′) of pairwise adjacent vertices in G′. The Strong Perfect Graph Conjecture asserts that a graph G is perfect if, and only if, neither G nor its complement ? contains an odd chordless cycle of length at least five. We prove that the conjecture is true for a class of P₅-free graphs.     

Orientation distance graphs

For two nonisomorphic orientations D and D′ of a graph G, the orientation distance d_o(D,D′) between D and D′ is the minimum number of arcs of D whose directions must be reversed to produce an orientation isomorphic to D′. The orientation distance graph 𝒟_o(G) of G has the set 𝒪(G) of pairwise nonisomorphic orientations of G as its vertex set and two vertices D and D′ of 𝒟₀(G) are adjacent if and only if d_o(D,D′) = 1. For a nonempty subset S of 𝒪(G), the orientation distance graph 𝒟₀(S) of S is the induced subgraph 〈S〉 of 𝒟_o(G). A graph H is an orientation distance graph if there exists a graph G and a set S⊆ 𝒪(G) such that 𝒟_o(S) is isomorphic to H. In this case, H is said to be an orientation distance graph with respect to G. This paper deals primarily with orientation distance graphs with respect to paths. For every integer n ≥ 4, it is shown that 𝒟_o(P_n) is Hamiltonian if and only if n is even. Also, the orientation distance graph of a path of odd order is bipartite. Furthermore, every tree is an orientation distance graph with respect to some path, as is every cycle, and for n ≥ 3 the clique number of 𝒟_o(P_n) is 2 if n is odd and is 3 otherwise. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 230–241, 2001     

Test sets for generalized matrix functions

Let G = (V,E) be a biconnected graph and let C be a cycle in G. The subgraphs of G identified with the biconnected components of the contraction of C in G are called the bridges of C. Associated with the set of bridges of a cycle C is an auxilliary graphical structure G_C called a bridge graph or an overlap graph. Such auxilliary graphs have provided important insights in classical graph theory, algorithmic graph theory, and complexity theory. In this paper, we use techniques from algorithmic combinatorics and complexity theory to derive canonical forms for cycles in bridge graphs. These canonical forms clarify the relationship between cycles in bridge graphs, the structure of the underlying graph G, and lexicographic order relations on the vertices of attachment of bridges of a cycle. The first canonical form deals with the structure of induced bridge graph cycles of length greater than three. Cycles of length three in bridge graphs are studied from a different point of view, namely that of the characterization of minimal elements in certain related posets: ordered bridge three-cycles (10 minimal elements), bridge three-cycles (5 minimal elements), bridge deletion three-cycles (infinite number, 7 classes), minor order (K ₅ K _3,3), chordal bridge three-cycles (13 minimal elements), contraction poset (5 minimal elements), cycle-minor poset (infinite number, 14 classes). These results, each giving a different insight into the structure of bridge three-cycles, follow as corollaries from the characterization of the 10 minimal elements of the ordered bridge three-cycle poset. This characterization is constructive and may be regarded as an extension of the classical Kuratowski's Theorem which follows as a corollary. Algorithms are described for constructing these various minimal elements in time O(∣E∣) or O(∣V∣) depending on the case. The first canonical form gives a constructive proof of the result that a graph is nonplanar if and only if it has a cycle C whose bridge graph G_C (alternatively, skew bridge graph) has a three-cycle. An algorithm is described that constructs this three-cycle in time O(∣E∣). This is best possible.     

A note on the girth‐doubling construction for polygonal graphs

A near‐polygonal graph is a graph Γ which has a set ?? of m‐cycles for some positive integer m such that each 2‐path of Γ is contained in exactly one cycle in ??. If m is the girth of Γ then the graph is called polygonal. Given a polygonal graph Γ of valency r and girth m, Archdeacon and Perkel proved the existence of a polygonal graph Γ₂ of valency r and girth 2m. We will show that this construction can be extended to one that yields a polygonal graph Γ₃ of valency r and girth 3m, but that making the cycles any longer with this construction does not yield a polygonal graph. We also show that if Aut(Γ) is 2‐arc transitive, so is Aut(Γ_k) for k = 2, 3. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 246‐254, 2011     

Minimum C5‐saturated graphs

A graph is C₅‐saturated if it has no five‐cycle as a subgraph, but does contain a C₅ after the addition of any new edge. We prove that the minimum number of edges in a C₅ ‐saturated graph on n≥11 vertices is sat(n, C₅)=?10(n?1)/7??1 if n∈N₀={11, 12, 13, 14, 16, 18, 20} and is ?10(n?1)/7? if n≥11 and n?N₀. © 2009 Wiley Periodicals, Inc. J Graph Theory     

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     

Minimum Degree Conditions for Cycles Including Specified Sets of Vertices

This paper generalises the concept of vertex pancyclic graphs. We define a graph as set-pancyclic if for every set S of vertices there is a cycle of every possible length containing S. We show that if the minimum degree of a graph exceeds half its order then the graph is set-pancyclic. We define a graph as k-ordered-pancyclic if, for every set S of cardinality k and every cyclic ordering of S, there is for every possible length a cycle of that length containing S and encountering S in the specified order. We determine the best possible minimum-degree condition which guarantees that a graph is k-ordered-pancyclic.