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.     

Finite 2‐Geodesic Transitive Graphs of Prime Valency

We classify noncomplete prime valency graphs satisfying the property that their automorphism group is transitive on both the set of arcs and the set of 2‐geodesics. We prove that either Γ is 2‐arc transitive or the valency p satisfies , and for each such prime there is a unique graph with this property: it is a nonbipartite antipodal double cover of the complete graph with automorphism group and diameter 3.     

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.     

Completing orientations of partially oriented graphs

We initiate a general study of what we call orientation completion problems. For a fixed class of oriented graphs, the orientation completion problem asks whether a given partially oriented graph P can be completed to an oriented graph in by orienting the (nonoriented) edges in P. Orientation completion problems commonly generalize several existing problems including recognition of certain classes of graphs and digraphs as well as extending representations of certain geometrically representable graphs. We study orientation completion problems for various classes of oriented graphs, including k‐arc‐strong oriented graphs, k‐strong oriented graphs, quasi‐transitive‐oriented graphs, local tournaments, acyclic local tournaments, locally transitive tournaments, locally transitive local tournaments, in‐tournaments, and oriented graphs that have directed cycle factors. We show that the orientation completion problem for each of these classes is either polynomial time solvable or NP‐complete. We also show that some of the NP‐complete problems become polynomial time solvable when the input‐oriented graphs satisfy certain extra conditions. Our results imply that the representation extension problems for proper interval graphs and for proper circular arc graphs are polynomial time solvable. The latter generalizes a previous result.     

The 2‐surviving rate of planar graphs with average degree lower than

Let G be any connected graph on n vertices, . Let k be any positive integer. Suppose that a fire breaks out at some vertex of G. Then, in each turn firefighters can protect at most k vertices of G not yet on fire; Next the fire spreads to all unprotected neighbors of burning vertices. The k‐surviving rate of G, denoted by , is the expected fraction of vertices that can be saved from the fire, provided that the starting vertex is chosen uniformly at random. In this note, it is shown that for any planar graph G with average degree , where , there is . In particular, the result implies a significant improvement of the bound for 2‐surviving rate for triangle‐free planar graphs (Esperet et al.  3 ) and for planar graphs without 4‐cycles (Kong et al.  12 ). The proof is done using the separator theorem for planar graphs.     

Classification of Vertex‐Transitive Cubic Partial Cubes

Partial cubes are graphs isometrically embeddable into hypercubes. In this article, it is proved that every cubic, vertex‐transitive partial cube is isomorphic to one of the following graphs: , for , the generalized Petersen graph G (10, 3), the cubic permutahedron, the truncated cuboctahedron, or the truncated icosidodecahedron. This classification is a generalization of results of Bre?ar et  al. (Eur J Combin 25 (2004), 55–64) on cubic mirror graphs; it includes all cubic, distance‐regular partial cubes (P. M. Weichsel, Discrete Math 109 (1992), 297–306), and presents a contribution to the classification of all cubic partial cubes.     

Equimatchable Graphs on Surfaces

A graph G is equimatchable if each matching in G is a subset of a maximum‐size matching and it is factor critical if has a perfect matching for each vertex v of G. It is known that any 2‐connected equimatchable graph is either bipartite or factor critical. We prove that for 2‐connected factor‐critical equimatchable graph G the graph is either or for some n for any vertex v of G and any minimal matching M such that is a component of . We use this result to improve the upper bounds on the maximum number of vertices of 2‐connected equimatchable factor‐critical graphs embeddable in the orientable surface of genus g to if and to if . Moreover, for any nonnegative integer g we construct a 2‐connected equimatchable factor‐critical graph with genus g and more than vertices, which establishes that the maximum size of such graphs is . Similar bounds are obtained also for nonorientable surfaces. In the bipartite case for any nonnegative integers g, h, and k we provide a construction of arbitrarily large 2‐connected equimatchable bipartite graphs with orientable genus g, respectively nonorientable genus h, and a genus embedding with face‐width k. Finally, we prove that any d‐degenerate 2‐connected equimatchable factor‐critical graph has at most vertices, where a graph is d‐degenerate if every its induced subgraph contains a vertex of degree at most d.     

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 .     

Flag‐transitive 2‐ designs of product type

In this paper, we prove that if a 2‐ design admits a flag‐transitive automorphism group G, then G is of affine, almost simple type, or product type. Furthermore, we prove that if G is product type then is either a 2‐(25, 4, 12) design or a 2‐(25, 4, 18) design with .     

Partition functions and a generalized coloring‐flow duality for embedded graphs

Let G be a finite group and a class function. Let be a directed graph with for each vertex a cyclic order of the edges incident to it. The cyclic orders give a collection F of faces of H. Define the partition function , where denotes the product of the κ‐values of the edges incident with v (in cyclic order), where the inverse is taken for edges leaving v. Write , where the sum runs over irreducible representations λ of G with character and with for every λ. When H is connected, it is proved that , where 1 is the identity element of G. Among the corollaries, a formula for the number of nowhere‐identity G‐flows on H is derived, generalizing a result of Tutte. We show that these flows correspond bijectively to certain proper G‐colorings of a covering graph of the dual graph of H. This correspondence generalizes coloring‐flow duality for planar graphs.     

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.     

The complete bipartite graphs with a unique edge‐transitive embedding

Jones, Nedela, and Škoviera (2008) showed that a complete bipartite graph has a unique orientably regular embedding if and only if . In this article, we extend this result by proving that a complete bipartite graph has a unique orientably edge‐transitive embedding if and only if .     

Minimal Obstructions for 1‐Immersions and Hardness of 1‐Planarity Testing

A graph is 1‐planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge (and any pair of crossing edges cross only once). A non‐1‐planar graph G is minimal if the graph is 1‐planar for every edge e of G. We construct two infinite families of minimal non‐1‐planar graphs and show that for every integer , there are at least nonisomorphic minimal non‐1‐planar graphs of order n. It is also proved that testing 1‐planarity is NP‐complete.     

Cores of Imprimitive Symmetric Graphs of Order a Product of Two Distinct Primes

A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G‐symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G‐symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given.     

Perfect Digraphs

The clique number of a digraph D is the size of the largest bidirectionally complete subdigraph of D. D is perfect if, for any induced subdigraph H of D, the dichromatic number defined by Neumann‐Lara (The dichromatic number of a digraph, J. Combin. Theory Ser. B 33 (1982), 265–270) equals the clique number . Using the Strong Perfect Graph Theorem (M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. Math. 164 (2006), 51–229) we give a characterization of perfect digraphs by a set of forbidden induced subdigraphs. Modifying a recent proof of Bang‐Jensen et al. (Finding an induced subdivision of a digraph, Theoret. Comput. Sci. 443 (2012), 10–24) we show that the recognition of perfect digraphs is co‐‐complete. It turns out that perfect digraphs are exactly the complements of clique‐acyclic superorientations of perfect graphs. Thus, we obtain as a corollary that complements of perfect digraphs have a kernel, using a result of Boros and Gurvich (Perfect graphs are kernel solvable, Discrete Math. 159 (1996), 35–55). Finally, we prove that it is ‐complete to decide whether a perfect digraph has a kernel.     

Independent Domination in Cubic Graphs

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by , is the minimum cardinality of an independent dominating set. In this article, we show that if is a connected cubic graph of order n that does not have a subgraph isomorphic to K_{2, 3}, then . As a consequence of our main result, we deduce Reed's important result [Combin Probab Comput 5 (1996), 277–295] that if G is a cubic graph of order n, then , where denotes the domination number of G.     

Nonseparating K4‐subdivisions in graphs of minimum degree at least 4

We first prove that for every vertex x of a 4‐connected graph G, there exists a subgraph H in G isomorphic to a subdivision of the complete graph K₄ on four vertices such that is connected and contains x. This implies an affirmative answer to a question of Kühnel whether every 4‐connected graph G contains a subdivision H of K₄ as a subgraph such that is connected. The motor for our induction is a result of Fontet and Martinov stating that every 4‐connected graph can be reduced to a smaller one by contracting a single edge, unless the graph is the square of a cycle or the line graph of a cubic graph. It turns out that this is the only ingredient of the proof where 4‐connectedness is used. We then generalize our result to connected graphs of minimum degree at least 4 by developing the respective motor, a structure theorem for the class of simple connected graphs of minimum degree at least 4. A simple connected graph G of minimum degree 4 cannot be reduced to a smaller such graph by deleting a single edge or contracting a single edge and simplifying if and only if it is the square of a cycle or the edge disjoint union of copies of certain bricks as follows: Each brick is isomorphic to K₃, K₅, K_{2, 2, 2}, , , or one the four graphs , , , obtained from K₅ and K_{2, 2, 2} by deleting the edges of a triangle, or replacing a vertex x by two new vertices and adding four edges to the endpoints of two disjoint edges of its former neighborhood, respectively. Bricks isomorphic to K₅ or K_{2, 2, 2} share exactly one vertex with the other bricks of the decomposition, vertices of degree 4 in any other brick are not contained in any further brick of the decomposition, and the vertices of a brick isomorphic to K₃ must have degree 4 in G and have pairwise no common neighbors outside that brick.     

Counterexamples to the List Square Coloring Conjecture

The square G² of a graph G is the graph defined on such that two vertices u and v are adjacent in G² if the distance between u and v in G is at most 2. Let and be the chromatic number and the list chromatic number of a graph H, respectively. A graph H is called chromatic‐choosable if . It is an interesting problem to find graphs that are chromatic‐choosable. Kostochka and Woodall (Choosability conjectures and multicircuits, Discrete Math., 240 (2001), 123–143) conjectured that for every graph G, which is called List Square Coloring Conjecture. In this article, we give infinitely many counter examples to the conjecture. Moreover, we show that the value can be arbitrarily large.     

Edge‐colorings avoiding rainbow stars

We consider an extremal problem motivated by a article of Balogh [J. Balogh, A remark on the number of edge colorings of graphs, European Journal of Combinatorics 27, 2006, 565–573], who considered edge‐colorings of graphs avoiding fixed subgraphs with a prescribed coloring. More precisely, given , we look for n‐vertex graphs that admit the maximum number of r‐edge‐colorings such that at most colors appear in edges incident with each vertex, that is, r‐edge‐colorings avoiding rainbow‐colored stars with t edges. For large n, we show that, with the exception of the case , the complete graph is always the unique extremal graph. We also consider generalizations of this problem.     

Graph operations and upper bounds on graph homomorphism counts

We construct a family of countexamples to a conjecture of Galvin [5], which stated that for any n‐vertex, d‐regular graph G and any graph H (possibly with loops), where is the number of homomorphisms from G to H. By exploiting properties of the graph tensor product and graph exponentiation, we also find new infinite families of H for which the bound stated above on holds for all n‐vertex, d‐regular G. In particular, we show that if H_WR is the complete looped path on three vertices, also known as the Widom–Rowlinson graph, then for all n‐vertex, d‐regular G. This verifies a conjecture of Galvin.