Unitary Graphs

Unitary graphs are arc‐transitive graphs with vertices the flags of Hermitian unitals and edges defined by certain elements of the underlying finite fields. They played a significant role in a recent classification of a class of arc‐transitive graphs that admit an automorphism group acting imprimitively on the vertices. In this article, we prove that all unitary graphs are connected of diameter two and girth three. Based on this, we obtain, for any prime power , a lower bound of order on the maximum number of vertices in an arc‐transitive graph of degree and diameter two.     

Two‐sided Group Digraphs and Graphs

We study a family of digraphs (directed graphs) that generalises the class of Cayley digraphs. For nonempty subsets of a group G, we define the two‐sided group digraph to have vertex set G, and an arc from x to y if and only if for some and . In common with Cayley graphs and digraphs, two‐sided group digraphs may be useful to model networks as the same routing and communication scheme can be implemented at each vertex. We determine necessary and sufficient conditions on L and R under which may be viewed as a simple graph of valency , and we call such graphs two‐sided group graphs. We also give sufficient conditions for two‐sided group digraphs to be connected, vertex‐transitive, or Cayley graphs. Several open problems are posed. Many examples are given, including one on 12 vertices with connected components of sizes 4 and 8.     

Structure Theorem for U5‐free Tournaments

Let U₅ be the tournament with vertices v₁, …, v₅ such that , and if , and . In this article, we describe the tournaments that do not have U₅ as a subtournament. Specifically, we show that if a tournament G is “prime”—that is, if there is no subset , , such that for all , either for all or for all —then G is U₅‐free if and only if either G is a specific tournament or can be partitioned into sets X, Y, Z such that , , and are transitive. From the prime U₅‐free tournaments we can construct all the U₅‐free tournaments. We use the theorem to show that every U₅‐free tournament with n vertices has a transitive subtournament with at least vertices, and that this bound is tight.     

Improper Coloring of Sparse Graphs with a Given Girth,II: Constructions

A graph G is ‐colorable if can be partitioned into two sets and so that the maximum degree of is at most j and of is at most k. While the problem of verifying whether a graph is (0, 0)‐colorable is easy, the similar problem with in place of (0, 0) is NP‐complete for all nonnegative j and k with . Let denote the supremum of all x such that for some constant every graph G with girth g and for every is ‐colorable. It was proved recently that . In a companion paper, we find the exact value . In this article, we show that increasing g from 5 further on does not increase much. Our constructions show that for every g, . We also find exact values of for all g and all .     

On Rooted Packings,Decompositions, and Factors of Graphs

In this article, we study so‐called rooted packings of rooted graphs. This concept is a mutual generalization of the concepts of a vertex packing and an edge packing of a graph. A rooted graph is a pair , where G is a graph and . Two rooted graphs and are isomorphic if there is an isomorphism of the graphs G and H such that S is the image of T in this isomorphism. A rooted graph is a rooted subgraph of a rooted graph if H is a subgraph of G and . By a rooted ‐packing into a rooted graph we mean a collection of rooted subgraphs of isomorphic to such that the sets of edges are pairwise disjoint and the sets are pairwise disjoint. In this article, we concentrate on studying maximum ‐packings when H is a star. We give a complete classification with respect to the computational complexity status of the problems of finding a maximum ‐packing of a rooted graph when H is a star. The most interesting polynomial case is the case when H is the 2‐edge star and S contains the center of the star only. We prove a min–max theorem for ‐packings in this case.     

Face 2‐Colorable Embeddings with Faces of Specified Lengths

Suppose and are arbitrary lists of positive integers. In this article, we determine necessary and sufficient conditions on M and N for the existence of a simple graph G, which admits a face 2‐colorable planar embedding in which the faces of one color have boundary lengths and the faces of the other color have boundary lengths . Such a graph is said to have a planar ‐biembedding. We also determine necessary and sufficient conditions on M and N for the existence of a simple graph G whose edge set can be partitioned into r cycles of lengths and also into t cycles of lengths . Such a graph is said to be ‐decomposable.     

Minors in ‐ Chromatic Graphs,II

Let denote the graph obtained from the complete graph by deleting the edges of some ‐subgraph. The author proved earlier that for each fixed s and , every graph with chromatic number has a minor. This confirmed a partial case of the corresponding conjecture by Woodall and Seymour. In this paper, we show that the statement holds already for much smaller t, namely, for .     

On the Circular Chromatic Number of Graph Powers

This article intends to study some functors from the category of graphs to itself such that, for any graph G, the circular chromatic number of is determined by that of G. In this regard, we investigate some coloring properties of graph powers. We show that provided that . As a consequence, we show that if , then . In particular, and has no subgraph with circular chromatic number equal to . This provides a negative answer to a question asked in (X. Zhu, Discrete Math, 229(1–3) (2001), 371–410). Moreover, we investigate the nth multichromatic number of subdivision graphs. Also, we present an upper bound for the fractional chromatic number of subdivision graphs. Precisely, we show that .     

Saturation numbers for families of graph subdivisions

For a family of graphs, a graph G is ‐saturated if G contains no member of as a subgraph, but for any edge in , contains some member of as a subgraph. The minimum number of edges in an ‐saturated graph of order n is denoted . A subdivision of a graph H, or an H‐subdivision, is a graph G obtained from H by replacing the edges of H with internally disjoint paths of arbitrary length. We let denote the family of H‐subdivisions, including H itself. In this paper, we study when H is one of or , obtaining several exact results and bounds. In particular, we determine exactly for and show for n sufficiently large that there exists a constant such that . For we show that will suffice, and that this can be improved slightly depending on the value of . We also give an upper bound on for all t and show that . This provides an interesting contrast to a 1937 result of Wagner (Math Ann, 114 (1937), 570–590), who showed that edge‐maximal graphs without a K₅‐minor have at least edges.     

Finding for a Surface Σ of Characteristic −4

For each surface Σ, we define max G is a class two graph of maximum degree that can be embedded in . Hence, Vizing's Planar Graph Conjecture can be restated as if Σ is a sphere. In this article, by applying some newly obtained adjacency lemmas, we show that if Σ is a surface of characteristic . Until now, all known satisfy . This is the first case where .     

Orientable Hamilton Cycle Embeddings of Complete Tripartite Graphs II: Voltage Graph Constructions and Applications

In an earlier article the authors constructed a hamilton cycle embedding of in a nonorientable surface for all and then used these embeddings to determine the genus of some large families of graphs. In this two‐part series, we extend those results to orientable surfaces for all . In part II, a voltage graph construction is presented for building embeddings of the complete tripartite graph on an orientable surface such that the boundary of every face is a hamilton cycle. This construction works for all such that p is prime, completing the proof started by part I (which covers the case ) that there exists an orientable hamilton cycle embedding of for all , . These embeddings are then used to determine the genus of several families of graphs, notably for and, in some cases, for .     

The Set of Circular Flow Numbers of Regular Graphs

This article determines the set of the circular flow numbers of regular graphs. Let be the set of the circular flow numbers of graphs, and be the set of the circular flow numbers of d‐regular graphs. If d is even, then . For it is known 6 that . We show that . Hence, the interval is the only gap for circular flow numbers of ‐regular graphs between and 5. Furthermore, if Tutte's 5‐flow conjecture is false, then it follows, that gaps for circular flow numbers of graphs in the interval [5, 6] are due for all graphs not just for regular graphs.     

The Degree‐Diameter Problem for Claw‐Free Graphs and Hypergraphs

We study the degree‐diameter problem for claw‐free graphs and 2‐regular hypergraphs. Let be the largest order of a claw‐free graph of maximum degree Δ and diameter D. We show that , where , for any D and any even . So for claw‐free graphs, the well‐known Moore bound can be strengthened considerably. We further show that for with (mod 4). We also give an upper bound on the order of ‐free graphs of given maximum degree and diameter for . We prove similar results for the hypergraph version of the degree‐diameter problem. The hypergraph Moore bound states that the order of a hypergraph of maximum degree Δ, rank k, and diameter D is at most . For 2‐regular hypergraph of rank and any diameter D, we improve this bound to , where . Our construction of claw‐free graphs of diameter 2 yields a similar result for hypergraphs of diameter 2, degree 2, and any even rank .     

On the Multichromatic Number of s‐Stable Kneser Graphs

For positive integers n and s, a subset [n] is s‐stable if for distinct . The s‐stable r‐uniform Kneser hypergraph is the r‐uniform hypergraph that has the collection of all s‐stable k‐element subsets of [n] as vertex set and whose edges are formed by the r‐tuples of disjoint s‐stable k‐element subsets of [n]. Meunier ( 21 ) conjectured that for positive integers with , and , the chromatic number of s‐stable r ‐uniform Kneser hypergraphs is equal to . It is a generalized version of the conjecture proposed by Alon et al. ( 1 ). Alon et al. ( 1 ) confirmed Meunier's conjecture for with arbitrary positive integer q. Lin et al. ( 17 ) studied the kth chromatic number of the Mycielskian of the ordinary Kneser graphs for . They conjectured that for . The case was proved by Mycielski ( 22 ). Lin et al. ( 17 ) confirmed their conjecture for , or when n is a multiple of k or . In this paper, we investigate the multichromatic number of the usual s ‐stable Kneser graphs . With the help of Fan's (1952) combinatorial lemma, we show that Meunier's conjecture is true for r is a power of 2 and s is a multiple of r, and Lin‐Liu‐Zhu's conjecture is true for .     

2‐Distance Coloring of Sparse Graphs

For graphs of bounded maximum average degree, we consider the problem of 2‐distance coloring, that is, the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. We prove that graphs with maximum average degree less than and maximum degree Δ at least 4 are 2‐distance ‐colorable, which is optimal and improves previous results from Dolama and Sopena, and from Borodin et al. We also prove that graphs with maximum average degree less than (resp. , ) and maximum degree Δ at least 5 (resp. 6, 8) are list 2‐distance ‐colorable, which improves previous results from Borodin et al., and from Ivanova. We prove that any graph with maximum average degree m less than and with large enough maximum degree Δ (depending only on m) can be list 2‐distance ‐colored. There exist graphs with arbitrarily large maximum degree and maximum average degree less than 3 that cannot be 2‐distance ‐colored: the question of what happens between and 3 remains open. We prove also that any graph with maximum average degree can be list 2‐distance ‐colored (C depending only on m). It is optimal as there exist graphs with arbitrarily large maximum degree and maximum average degree less than 4 that cannot be 2‐distance colored with less than colors. Most of the above results can be transposed to injective list coloring with one color less.     

The Images of the Clique Operator and Its Square are Different

Let be the class of all graphs and K be the clique operator. The validity of the equality has been an open question for several years. A graph in but not in is exhibited here.     

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      

Generating Nonisomorphic Quadrangular Embeddings of a Complete Graph

We construct (resp. ) index one current graphs with current group such that the current graphs have different underlying graphs and generate nonisomorphic orientable (resp. nonorientable) quadrangular embeddings of the complete graph , (resp. ).     

Spanning Trees with Vertices Having Large Degrees

Let G be a connected simple graph, and let f be a mapping from to the set of integers. This paper is concerned with the existence of a spanning tree in which each vertex v has degree at least . We show that if for any nonempty subset , then a connected graph G has a spanning tree such that for all , where is the set of neighbors v of vertices in S with , , and is the degree of x in T. This is an improvement of several results, and the condition is best possible.