Hypotraceable digraphs

A hypotraceable digraph is a digraph D = (V, E) which is not traceable, i.e., does not contain a (directed)Hamiltonian path, but for which D - v is traceable for all ve ∈ V. We prove that a hypotraceable digraph of order n exists iff n ≥ 7 and that for each k ≥ 3 there are infinitely many hypotraceable oriented graphs with a source and a sink and precisely k strong components. We also show that there are strongly connected hypotraceable oriented graphs and that there are hypotraceable digraphs with precisely two strong components one of which is a source or a sink. Finally, we prove that hypo-Hamiltonian and hypotraceable digraphs may contain large complete subdigraphs.     

The order of hypotraceable oriented graphs

A digraph of order n is hypotraceable if it is nontraceable but all its induced subdigraphs of order n−1 are traceable. Grötschel et al. (1980) [M. Grötschel, C. Thomassen, Y. Wakabayashi, Hypotraceable digraphs, J. Graph Theory 4 (1980) 377–381] constructed an infinite family of hypotraceable oriented graphs, the smallest of which has order 13. We show that there exist hypotraceable oriented graphs of order n for every n≥8 except possibly for n=9,11 and that is the only one of order less than 8.Furthermore, we determine all the hypotraceable oriented graphs of order 8 and explain the relevance of these results to the problem of determining, for given k≥2, the maximum order of nontraceable oriented digraphs each of whose induced subdigraphs of order k is traceable.     

Finding an induced subdivision of a digraph

We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) H, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether H is an oriented graph or contains 2-cycles. We announce a number of examples of polynomial instances as well as several NP-completeness results.     

Maximum Directed Cuts in Graphs with Degree Constraints

The Max Cut problem is an NP-hard problem and has been studied extensively. Alon et?al. (J Graph Theory 55:1–13, 2007) studied a directed version of the Max Cut problem and observed its connection to the Hall ratio of graphs. They proved, among others, that if an acyclic digraph has m edges and each vertex has indegree or outdegree at most 1, then it has a directed cut of size at least 2m/5. Lehel et?al. (J Graph Theory 61:140–156, 2009) extended this result by replacing the “acyclic digraphs” with the “digraphs containing no directed triangles”. In this paper, we characterize the acyclic digraphs with m edges whose maximum dicuts have exactly 2m/5 edges, and our approach gives an alternative proof of the result of Lehel et?al. We also show that there are infinitely many positive rational numbers β < 2/5 for which there exist digraphs D (with directed triangles) such that each vertex of D has indegree or outdegree at most 1, and any maximum directed cut in D has size precisely β|E(D)|.     

Sufficient Conditions for Super-Arc-Strongly Connected Oriented Graphs

A digraph D is called super-arc-strongly connected if the arcs of every its minimum arc-disconnected set are incident to or from some vertex in D. A digraph without any directed cycle of length 2 is called an oriented graph. Sufficient conditions for digraphs to be super-arc-strongly connected have been given by several authors. However, closely related conditions for super-arc-strongly connected oriented graphs have little attention until now. In this paper we present some minimum degree and degree sequence conditions for oriented graphs to be super-arc-strongly connected.     

Planar cubic hypohamiltonian and hypotraceable graphs

Infinite families of planar cubic hypohamiltonian and hypotraceable graphs are described and these are used to prove that the maximum degree and the maximum number of edges in a hypohamiltonian graph with n vertices are approximately $\text{n}\text{2}$ and $\text{n}{}^2\text{4}$, respectively. Also, the possible order of a cubic hypohamiltonian graph is determined.     

Descendant-homogeneous digraphs

The descendant setdesc(α) of a vertex α in a digraph D is the set of vertices which can be reached by a directed path from α. A subdigraph of D is finitely generated if it is the union of finitely many descendant sets, and D is descendant-homogeneous if it is vertex transitive and any isomorphism between finitely generated subdigraphs extends to an automorphism. We consider connected descendant-homogeneous digraphs with finite out-valency, specially those which are also highly arc-transitive. We show that these digraphs must be imprimitive. In particular, we study those which can be mapped homomorphically onto Z and show that their descendant sets have only one end.There are examples of descendant-homogeneous digraphs whose descendant sets are rooted trees. We show that these are highly arc-transitive and do not admit a homomorphism onto Z. The first example (Evans (1997) [6]) known to the authors of a descendant-homogeneous digraph (which led us to formulate the definition) is of this type. We construct infinitely many other descendant-homogeneous digraphs, and also uncountably many digraphs whose descendant sets are rooted trees but which are descendant-homogeneous only in a weaker sense, and give a number of other examples.     

Maximum diameter of regular digraphs

We prove that every r-biregular digraph with n vertices has its directed diamter bounded by (3n - r - 3)/(r +1). We show that this bound is tight for directed as well as for undirected graphs. The upper bound remains valid for Eulerian digraphs with minimum outdegree r. © 1929 John Wiley & Sons, Inc.     

New constructions of hypohamiltonian and hypotraceable graphs

A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex‐deleted subgraphs of G are hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so‐called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex‐deleted subgraphs are hamiltonian with exactly one exception, see [15]). This construction is an extension of a method of Thomassen [11]. As an application, we construct a planar hypotraceable graph of order 138, improving the best‐known bound of 154 [8]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method. We also prove that if G is a Grinbergian graph without a triangular region, then G is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best‐known bound of 46 [14].     

Planar and infinite hypohamiltonian and hypotraceable graphs

Chvátal raised the question whether or not planar hypohamiltonian graphs exist and Grünbaum conjectured the nonexistence of such graphs. We shall describe an infinite class of planar hypohamiltonian graphs and infinite classes of planar hypotraceable graphs of connectivity two (resp. three). Infinite hypohamiltonian (resp. htpotraceable) graphs are also described. It is shown how the study of infinite hypotraceable graphs leads to a new infinite family of finite hypotraceable graphs.     

On large vertex-symmetric digraphs

There is special interest in the design of large vertex-symmetric graphs and digraphs as models of interconnection networks for implementing parallelism. In these systems, a large number of nodes are connected with relatively few links and short paths between the nodes, and each node may execute the same communication software without modifications.In this paper, a method for obtaining new general families of large vertex-symmetric digraphs is put forward. To be more precise, from a k-reachable vertex-symmetric digraph and another (k+1)-reachable digraph related to the previous one, and using a new special composition of digraphs, new families of vertex-symmetric digraphs with small diameter are presented. With these families we obtain new vertex-symmetric digraphs that improve various values of the table of the largest known vertex-symmetric (Δ,D)-digraphs. The paper also contains the (Δ,D)-table for vertex-symmetric digraphs, for Δ≤13 and D≤12.     

On the number of noncritical vertices in strongly connected digraphs

By definition, a vertex w of a strongly connected (or, simply, strong) digraph D is noncritical if the subgraph D — w is also strongly connected. We prove that if the minimal out (or in) degree k of D is at least 2, then there are at least k noncritical vertices in D. In contrast to the case of undirected graphs, this bound cannot be sharpened, for a given k, even for digraphs of large order. Moreover, we show that if the valency of any vertex of a strong digraph of order n is at least 3/4n, then it contains at least two noncritical vertices. The proof makes use of the results of the theory of maximal proper strong subgraphs established by Mader and developed by the present author. We also construct a counterpart of this theory for biconnected (undirected) graphs.     

Digraphs with real and gaussian spectra

The conventional binary operations of cartesian product, conjunction, and composition of two digraphs D₁ and D₂ are observed to give the sum, the product, and a more complicated combination of the spectra of D₁ and D₂ as the resulting spectrum. These formulas for analyzing the spectrum of a digraph are utilized to construct for any positive integer n, a collection of n nonisomorphic strong regular nonsymmetric digraphs with real spectra. Further, an infinite collection of strong nonsymmetric digraphs with nonzero gaussian integer value is found. Finally, for any n, it is shown that there are n cospectral strong nonsymmetric digraphs with integral spectra.     

Quasi-transitive digraphs

A digraph is quasi-transitive if there is a complete adjacency between the inset and the outset of each vertex. Quasi-transitive digraphs are interseting because of their relation to comparability graphs. Specifically, a graph can be oriented as a quasi-transitive digraph if and only if it is a comparability graph. Quasi-transitive digraphs are also of interest as they share many nice properties of tournaments. Indeed, we show that every strongly connected quasi-transitive digraphs D on at least four vertices has two vertices v₁ and v₂ such that D – v_i is strongly connected for i = 1, 2. A result of tournaments on the existence of a pair of arc-disjoint in- and out-branchings rooted at the same vertex can also be extended to quasi-transitive digraphs. However, some properties of tournaments, like hamiltonicity, cannot be extended directly to quasi-transitive digraphs. Therefore we characterize those quasi-transitive digraphs which have a hamiltonian cycle, respectively a hamiltonian path. We show the existence of highly connected quasi-transitive digraphs D with a factor (a collection of disjoint cycles covering the vertex set of D), which have a cycle of every length 3 ≦ k ≦ |V(D)| ? 1 through every vertex and yet they are not hamiltonian. Finally we characterize pancyclic and vertex pancyclic quasi-transitive digraphs. © 1995, John Wiley & Sons, Inc.     

Some sufficient conditions for the existence of kernels in infinite digraphs

A kernel N of a digraph D is an independent set of vertices of D such that for every w∈V(D)−N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel perfect digraph. D is called a critical kernel imperfect digraph when D has no kernel but every proper induced subdigraph of D has a kernel. If F is a set of arcs of D, a semikernel modulo F of D is an independent set of vertices S of D such that for every z∈V(D)−S for which there exists an (S,z)-arc of D−F, there also exists an (z,S)-arc in D. In this work we show sufficient conditions for an infinite digraph to be a kernel perfect digraph, in terms of semikernel modulo F. As a consequence it is proved that symmetric infinite digraphs and bipartite infinite digraphs are kernel perfect digraphs. Also we give sufficient conditions for the following classes of infinite digraphs to be kernel perfect digraphs: transitive digraphs, quasi-transitive digraphs, right (or left)-pretransitive digraphs, the union of two right (or left)-pretransitive digraphs, the union of a right-pretransitive digraph with a left-pretransitive digraph, the union of two transitive digraphs, locally semicomplete digraphs and outward locally finite digraphs.     

Efficient total domination in digraphs

We generalize the concept of efficient total domination from graphs to digraphs. An efficiently total dominating set X of a digraph D is a vertex subset such that every vertex of D has exactly one predecessor in X. We study graphs that permit an orientation having such a set and give complexity results and characterizations. Furthermore, we study the computational complexity of the (weighted) efficient total domination problem for several digraph classes. In particular we deal with most of the common generalizations of tournaments, like locally semicomplete and arc-locally semicomplete digraphs.     

(p,q)-odd digraphs

A digraph D is (p,q)-odd if and only if any subdivision of D contains a directed cycle of length different from p mod q. A characterization of (p,q)-odd digraphs analogous to the Seymour-Thomassen characterization of (1, 2)-odd digraphs is provided. In order to obtain this characterization we study the lattice generated by the directed cycles of a strongly connected digraph. We show that the sets of directed cycles obtained from an ear decomposition of the digraph in a natural way are bases of this lattice. A similar result does not hold for undirected graphs. However we construct, for each undirected 2-connected graph G, a set of cycles of G which form a basis of the lattice generated by the cycles of G. © 1996 John Wiley & Sons, Inc.     

On planar hypohamiltonian graphs

We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer N, such that for every integer n≥N there exists a planar hypohamiltonian/hypotraceable graph on n vertices. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 55‐68, 2011     

Planar Hypohamiltonian Graphs on 40 Vertices

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer‐aided generation of certain families of planar graphs with girth 4 and a fixed number of 4‐faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.     

Spanning 2-strong tournaments in 3-strong semicomplete digraphs

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph on 2k vertices contains a spanning k-strong tournament.