Regular planar graphs with faces of only two types and shortness parameters

We construct a small non-Hamiltonian 3-connected trivalent planar graph whose faces are all 4-gons or 7-gons and show that the shortness coefficient of the class of such graphs is less than one. Then, by transforming non-Hamiltonian trivalent graphs into regular graphs of valency four or five, we obtain our main results, as follows. We show first that the class of 3-connected r-valent planar graphs whose faces are of only two types, triangles and q-gons, contains non-Hamiltonian members and has a shortness exponent less than one when r = 4, for all q ≧ 12. Under the extra restriction that, among graphs of connectivity three, only those with maximum cyclic edge-connectivity are to be considered, we prove the same result also when r = 4, for q = 20, and when r = 5, for all q ≧ 14 except multiples of three.     

Shortness parameters of families of regular planar graphs with two or three types of face

This paper is concerned with non-Hamiltonian planar graphs. It is shown that the class of 3-connected cubic planar graphs whose faces are all pentagons or 10-gons contains non-Hamiltonian members and that the shortness coefficient of this class of graphs is less than unity. For several classes of 3-connected regular planar graphs, of valency 4 or 5, it is shown that the shortness exponent is less than unity.     

On regular graphs and Hamiltonian circuits,including answers to some questions of Joseph Zaks

A graph is called l-ply Hamiltonian if it admits l edge-disjoint Hamiltonian circuits. The following results are obtained: (1) When n ≥ 3 and 0 ≤ 2l ≤ n there exists an n-connected n-regular graph that is exactly l-ply Hamiltonian. (2) There exist 5-connected 5-regular planar graphs that are not doubly (i.e. 2-ply) Hamiltonian, one with only 132 vertices and another with only three types of face, namely 3-, 4- and 12-gons. (3) There exist 3-connected 5-regular planar graphs, one that is non-Hamiltonian and has only 76 vertices and another that has no Hamiltonian paths and has only 128 vertices. (4) There exist 5-edge-connected 5-regular planar graphs, one that is non-Hamiltonian and has only 176 vertices and another that has no Hamiltonian paths and has only 512 vertices. Result (1) was known in the special cases $\text{l = [}\text{n}\text{2}\text{]}$ (an old result) and l = 0 (due to G. H. J. Meredith, 1973). The special case l = 1 provides a negative answer to question 4 in a recent paper by Joseph Zaks and implies Corollary 1 to Zaks' Theorem 1. Results (2) and (3) involve graphs with considerably fewer vertices (and, in one case, fewer types of face) than Zaks' corresponding graphs and provide partial answers to his questions 1 and 3. Result (4) involves graphs that satisfy a stronger condition than those of Zaks but still have fewer vertices.     

Cycle extendability in graphs and digraphs

In 1990, Hendry conjectured that all chordal Hamiltonian graphs are cycle extendable, that is, the vertices of each non-Hamiltonian cycle are contained in a cycle of length one greater. Let A be a symmetric (0,1)-matrix with zero main diagonal such that A is the adjacency matrix of a chordal Hamiltonian graph. Hendry’s conjecture in this case is that every k×k principle submatrix of A that dominates a full cycle permutation k×k matrix is a principle submatrix of a (k+1)×(k+1) principle submatrix of A that dominates a (k+1)×(k+1) full cycle permutation matrix. This article generalizes the concept of cycle-extendability to S-extendable; that is, with S⊆{1,2,…,n} and G a graph on n vertices, G is S-extendable if the vertices of every non-Hamiltonian cycle are contained in a cycle length i greater, where i∈S. We investigate this concept in directed graphs and in particular tournaments, i.e., anti-symmetric matrices with zero main diagonal.     

A note on the graph’s resolvent and the multifilar structure

We consider the recently discovered [V. Ejov, J.A. Filar, S.K. Lucas, P. Zograf, Clustering of spectra and fractals of regular graphs, J. Math. Anal. Appl. 333 (2007) 236-246] threadlike structure of the plot representing d-regular graphs in the mean-variance coordinates of exponential sums of the graph spectra. In this note we demonstrate that this self-similar phenomenon is more ubiquitous by exhibiting it with the help of a different generating function, namely the mean and the variance of the resolvent of the adjacency matrix of the graph. We also discuss the location of non-Hamiltonian graphs within this geometric structure.     

Maximal planar graphs of inscribable type and diagonal flips

A theorem due to Wagner states that given two maximal planar graphs with n vertices, one can be obtained from the other by performing a finite sequence of diagonal flips. In this paper, we show a result of a similar flavour—given two maximal planar graphs of inscribable type having the same vertex set, one can be obtained from the other by performing a finite sequence of diagonal flips such that all the intermediate graphs are of inscribable type.     

Maximally non-hamiltonian graphs of girth 7

We describe a sufficient condition for graphs used in a construction of Thomassen (which yields hypohamiltonian graphs) to produce maximally non-hamiltonian (MNH) graphs as well. Then we show that the Coxeter graph fulfils this sufficient condition, and thus applying the Thomassen's construction to multiple copies of the Coxeter graph yields infinitely many MNH graphs with girth 7. So far, the Coxeter graph was the only known example of a MNH graph of girth 7; also no MNH graph of girth greater than 7 has been found yet. Finally, the Isaacs' flower snarksJ _k for oddk 5 are shown to fulfil (for certain vertices) this sufficient condition as well.The research of author was partially supported by Grant No. 2/1138/94 Computational models, algorithms and complexity of Slovak Academy of Sciences and by EC Cooperative Action IC1000 Algorithms for Future Technologies (Project ALTEC)     

Are all simple 4-polytopes Hamiltonian?

We construct an extensive family of non-Hamiltonian, 4-regular, 4-connected graphs and show that none of these graphs is the graph of a simple 4-polytope. Support from NSERC and the Math. Dept. S.F.U. is gratefully acknowledged.     

Minimum Sum Coloring of P4-sparse graphs

In this paper, we study the Minimum Sum Coloring (MSC) problem on P₄-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. First, we introduce the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph. Next, based in such maximal sequences, we show that there is a large sub-family of P₄-sparse graphs for which the MSC problem can be solved in polynomial-time.     

Hamiltonicity of Amalgams

 An amalgam is obtained from two Halin graphs having skirting cycles of the same length. We are interested in hamiltonicity of amalgams constructed from two identical Halin graphs without any shift along the skirting cycle. We establish hamiltonicity of amalagams constructed from cubic Halin graphs. We give a sufficient condition for hamiltonicity of non-cubic amalgams and characterize infinite classes of non-Hamiltonian amalgams. We also characterize hamiltonicity of amalgams constructed by shifting the component Halin graphs by one and of general amalgams of higher degree. Received: June 23, 1997     

Shortness parameters for planar graphs with faces of only one type

We construct infinite sequences of non-Hamiltonian graphs and use them to show that the shortness exponent (or, in some cases, the shortness coefficient) is less than one for many classes of 3-connected planar graphs whose faces are all r-gons and whose vertices are all p-valent or q-valent, where p < q. Three of the five possible values of (r, p) are considered, namely (4.3). (3,3), and (3,4), in conjunction with most of the possible corresponding values of q.     

Polar graphs and maximal independent sets

We study two central problems of algorithmic graph theory: finding maximum and minimum maximal independent sets. Both problems are known to be NP-hard in general. Moreover, they remain NP-hard in many special classes of graphs. For instance, the problem of finding minimum maximal independent sets has been recently proven to be NP-hard in the class of so-called (1,2)-polar graphs. On the other hand, both problems can be solved in polynomial time for (1,1)-polar, also known as split graphs. In this paper, we address the question of distinguishing new classes of graphs admitting polynomial-time solutions for the two problems in question. To this end, we extend the hierarchy of (α,β)-polar graphs and study the computational complexity of the problems on polar graphs of special types.     

On the existence of certain distance-regular graphs

Distance-regular graphs of valency > 2, diameter m, and girth 2m with the additional property that any two points having maximal distance belong to a unique 2m circuit are investigated. It is shown that such graphs can exist only if m ≤ 3; if m = 3 only a finite number of valencies prove to be feasible.     

Wagner's theorem for Torus graphs

Wagner's theorem (any two maximal plane graphs having p vertices are equivalent under diagonal transformations) is extended to maximal torus graphs, graphs embedded in the torus with a maximal set of edges present. Thus any maximal torus graph having p vertices may be diagonally transformed into any other maximal torus graph having p vertices. As with Wagner's theorem, a normal form representing an intermediate stage in the above transformation is displayed. This result, along with Wagner's theorem, may make possible constructive characterizations of planar and toroidal graphs, through a wholly combinatorial definition of diagonal transformation.     

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

On Rauzy graph sequences of infinite words

Under study are the sequences of Rauzy graphs (i.e., the graphs of subwords overlapping) of infinite words. The k-stretching of a graph is the graph we obtain by replacing each edge with a chain of length k. Considering a sequence of strongly connected directed graphs of maximal in and out vertex degrees equal to s, we prove that it is, up to stretchings, a subsequence of a Rauzy graphs sequence of some uniformly recurrent infinite word on s-letter alphabet. The language of a word of this kind and stretching for a given sequence of graphs are constructed explicitly.     

Cyclically 5-edge-connected cubic planar graphs and shortness coefficients

It is shown that some classes of cyclically 5-edge-connected cubic planar graphs with only one type of face besides pentagons contain non-Hamiltonian members and have shortness coefficients less than unity.     

On the well-coveredness of Cartesian products of graphs

A graph G is well-covered if every maximal independent set has the same cardinality. This paper investigates when the Cartesian product of two graphs is well-covered. We prove that if G and H both belong to a large class of graphs that includes all non-well-covered triangle-free graphs and most well-covered triangle-free graphs, then G×H is not well-covered. We also show that if G is not well-covered, then neither is G×G. Finally, we show that G×G is not well-covered for all graphs of girth at least 5 by introducing super well-covered graphs and classifying all such graphs of girth at least 5.     

On Graphs Having Maximal Independent Sets of Exactly t Distinct Cardinalities

For a given positive integer t we consider graphs having maximal independent sets of precisely t distinct cardinalities and restrict our attention to those that have no vertices of degree one. In the situation when t is four or larger and the length of the shortest cycle is at least 6t ? 6, we completely characterize such graphs.