Leaf‐Critical and Leaf‐Stable Graphs

The minimum leaf number ml(G) of a connected graph G is defined as the minimum number of leaves of the spanning trees of G if G is not hamiltonian and 1 if G is hamiltonian. We study nonhamiltonian graphs with the property for each or for each . These graphs will be called ‐leaf‐critical and l‐leaf‐stable, respectively. It is far from obvious whether such graphs exist; for example, the existence of 3‐leaf‐critical graphs (that turn out to be the so‐called hypotraceable graphs) was an open problem until 1975. We show that l‐leaf‐stable and l‐leaf‐critical graphs exist for every integer , moreover for n sufficiently large, planar l‐leaf‐stable and l‐leaf‐critical graphs exist on n vertices. We also characterize 2‐fragments of leaf‐critical graphs generalizing a lemma of Thomassen. As an application of some of the leaf‐critical graphs constructed, we settle an open problem of Gargano et al. concerning spanning spiders. We also explore connections with a family of graphs introduced by Grünbaum in correspondence with the problem of finding graphs without concurrent longest paths.     

On Hypohamiltonian and Almost Hypohamiltonian Graphs

A graph G is almost hypohamiltonian if G is non‐hamiltonian, there exists a vertex w such that is non‐hamiltonian, and for any vertex the graph is hamiltonian. We prove the existence of an almost hypohamiltonian graph with 17 vertices and of a planar such graph with 39 vertices. Moreover, we find a 4‐connected almost hypohamiltonian graph, while Thomassen's question whether 4‐connected hypohamiltonian graphs exist remains open. We construct planar almost hypohamiltonian graphs of order n for every . During our investigation we draw connections between hypotraceable, hypohamiltonian, and almost hypohamiltonian graphs, and discuss a natural extension of almost hypohamiltonicity. Finally, we give a short argument disproving a conjecture of Chvátal (originally disproved by Thomassen), strengthen a result of Araya and Wiener on cubic planar hypohamiltonian graphs, and mention open problems.     

Hamiltonian Kneser Graphs

The Kneser graph K(n,k) has as vertices the k-subsets of {1, 2, ..., n}. Two vertices are adjacent if the corresponding k-subsets are disjoint. It was recently proved by the first author [2] that Kneser graphs have Hamilton cycles for n >= 3k. In this note, we give a short proof for the case when k divides n. Received September 14, 1999     

On s‐Hamiltonian Line Graphs

For an integer s ≥ 0, a graph G is s‐hamiltonian if for any vertex subset with |S^′| ≤ s, G ‐ S^′ is hamiltonian. It is well known that if a graph G is s‐hamiltonian, then G must be (s+2)‐connected. The converse is not true, as there exist arbitrarily highly connected nonhamiltonian graphs. But for line graphs, we prove that when s ≥ 5, a line graph is s‐hamiltonian if and only if it is (s+2)‐connected.     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

Vertex‐Transitive Graphs of Prime‐Squared Order Are Hamilton‐Decomposable

We prove that all connected vertex‐transitive graphs of order p², p a prime, can be decomposed into Hamilton cycles.     

Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u ₁ = v ₁, v = u _v(G) = v _v(G) , and u _i ≠ v _i for every 1 < i < v(G). A set of hamiltonian paths, {P ₁, P ₂, . . . , P _k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n–k ≥ 2. We use S _n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S _n,k ) = n–2 except for S _4,2 such that IHP(S _4,2) = 1.      

Non‐Critical Vertices and Long Circuits in Strong Tournaments of Order n and Diameter d

Let T be a strong tournament of order with diameter . A vertex w in T is non‐critical if the subtournament is also strong. In the opposite case, it is a critical vertex. In the present article, we show that T has at most critical vertices. This fact and Moon's vertex‐pancyclic theorem imply that for , it contains at least circuits of length . We describe the class of all strong tournaments of order with diameter for which this lower bound is achieved and show that for , the minimum number of circuits of length in a tournament of this class is equal to . In turn, the minimum among all strong tournaments of order with diameter 2 grows exponentially with respect to n for any given . Finally, for , we select a strong tournament of order n with diameter d and conjecture that for any strong tournament T of order n whose diameter does not exceed d, the number of circuits of length ? in T is not less than that in for each possible ?. Moreover, if these two numbers are equal to each other for some given , where , then T is isomorphic to either or its converse . For , this conjecture was proved by Las Vergnas. In the present article, we confirm it for the case . In an Appendix, some problems concerning non‐critical vertices are considered for generalizations of tournaments.     

Chordal 2‐Connected Graphs and Spanning Trees

We present a transformation on a chordal 2‐connected simple graph that decreases the number of spanning trees. Based on this transformation, we show that for positive integers n, m with , the threshold graph having n vertices and m edges that consists of an ‐clique and vertices of degree 2 is the only graph with the fewest spanning trees among all 2‐connected chordal graphs on n vertices and m edges.     

On the Turán number for the hexagon

A long-standing conjecture of Erd?s and Simonovits is that ex(n,C_2k), the maximum number of edges in an n-vertex graph without a 2k-gon is asymptotically as n tends to infinity. This was known almost 40 years ago in the case of quadrilaterals. In this paper, we construct a counterexample to the conjecture in the case of hexagons. For infinitely many n, we prove that

     

Perfect Graphs with No Balanced Skew‐Partition are 2‐Clique‐Colorable

A graph G is perfect if for all induced subgraphs H of G, . A graph G is Berge if neither G nor its complement contains an induced odd cycle of length at least five. The Strong Perfect Graph Theorem [9] states that a graph is perfect if and only if it is Berge. The Strong Perfect Graph Theorem was obtained as a consequence of a decomposition theorem for Berge graphs [M. Chudnovsky, Berge trigraphs and their applications, PhD thesis, Princeton University, 2003; M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann Math 164 (2006), 51–229.], and one of the decompositions in this decomposition theorem was the “balanced skew‐partition.” A clique‐coloring of a graph G is an assignment of colors to the vertices of G in such a way that no inclusion‐wise maximal clique of G of size at least two is monochromatic, and the clique‐chromatic number of G, denoted by , is the smallest number of colors needed to clique‐color G. There exist graphs of arbitrarily large clique‐chromatic number, but it is not known whether the clique‐chromatic number of perfect graphs is bounded. In this article, we prove that every perfect graph that does not admit a balanced skew‐partition is 2‐clique colorable. The main tool used in the proof is a decomposition theorem for “tame Berge trigraphs” due to Chudnovsky et al. ( http://arxiv.org/abs/1308.6444 ).     

Uniquely Cycle‐Saturated Graphs

Given a graph F, a graph G is uniquely F‐saturated if F is not a subgraph of G and adding any edge of the complement to G completes exactly one copy of F. In this article, we study uniquely ‐saturated graphs. We prove the following: (1) a graph is uniquely C₅‐saturated if and only if it is a friendship graph. (2) There are no uniquely C₆‐saturated graphs or uniquely C₇‐saturated graphs. (3) For , there are only finitely many uniquely ‐saturated graphs (we conjecture that in fact there are none). Additionally, our results show that there are finitely many k‐friendship graphs (as defined by Kotzig) for .     

Entropy bounds for perfect matchings and Hamiltonian cycles

For a graph G = (V,E) and x: E → ℜ⁺ satisfying Σ _e∋υ x _e = 1 for each υ ∈ V, set h(x) = Σ _e x _e log(1/x _e ) (with log = log₂). We show that for any n-vertex G, random (not necessarily uniform) perfect matching f satisfying a mild technical condition, and x _e =Pr(e∈f),

Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs

Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.     

On the Edit Distance from ‐Free Graphs

The edit distance between two graphs on the same vertex set is defined to be the size of the symmetric difference of their edge sets. The edit distance function of a hereditary property, , is a function of p, and measures, asymptotically, the furthest graph of edge density p from under this metric. In this article, we address the hereditary property , the property of having no induced copy of the complete bipartite graph with two vertices in one class and t in the other. Employing an assortment of techniques and colored regularity graph constructions, we are able to determine the edit distance function over the entire domain when and extend the interval over which the edit distance function for is known for all values of t, determining its maximum value for all odd t. We also prove that the function for odd t has a nontrivial interval on which it achieves its maximum. These are the only known principal hereditary properties for which this occurs. In the process of studying this class of functions, we encounter some surprising connections to extremal graph theory problems, such as strongly regular graphs and the problem of Zarankiewicz.     

On Triangle‐Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph

We prove a decomposition theorem for the class of triangle‐free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. We prove that every graph of girth at least five in this class is 3‐colorable.     

On semi‐classical d‐orthogonal polynomials

In this paper a general theory of semi‐classical d‐orthogonal polynomials is developed. We define the semi‐classical linear functionals by means of a distributional equation , where Φ and Ψ are matrix polynomials. Several characterizations for these semi‐classical functionals are given in terms of the corresponding d‐orthogonal polynomials sequence. They involve a quasi‐orthogonality property for their derivatives and some finite‐type relations.     

On 5‐Cycles and 6‐Cycles in Regular n‐Tournaments

Let T be a tournament of order n and be the number of cycles of length m in T. For and odd n, the maximum of is achieved for any regular tournament of order n (M. G. Kendall and B. Babington Smith, 1940), and in the case it is attained only for the unique regular locally transitive tournament RLT_n of order n (U. Colombo, 1964). A lower bound was also obtained for in the class of regular tournaments of order n (A. Kotzig, 1968). This bound is attained if and only if T is doubly regular (when ) or nearly doubly regular (when ) (B. Alspach and C. Tabib, 1982). In the present article, we show that for any regular tournament T of order n, the equality holds. This allows us to reduce the case to the case In turn, the pure spectral expression for obtained in the class implies that for a regular tournament T of order the inequality holds, with equality if and only if T is doubly regular or T is the unique regular tournament of order 7 that is neither doubly regular nor locally transitive. We also determine the value of c₆(RLT_n) and conjecture that this value coincides with the minimum number of 6‐cycles in the class for each odd      

Strong Circuit Double Cover of Some Cubic Graphs

Let C be a given circuit of a bridgeless cubic graph G. It was conjectured by Seymour that G has a circuit double cover (CDC) containing the given circuit C. This conjecture (strong CDC [SCDC] conjecture) has been verified by Fleischner and Häggkvist for various families of graphs and circuits. In this article, some of these earlier results have been improved: (1) if contains a Hamilton path or a Y‐tree of order less than 14, then G has a CDC containing C; (2) if is connected and , then G has a CDC containing C.