Polar cographs

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s,k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph (i.e., a collection of at most s disjoint stable sets with complete links between all sets) and B a disjoint union of at most k cliques (i.e., the complement of a complete k-partite graph).Recognizing a polar graph is known to be NP-complete. These graphs have not been extensively studied and no good characterization is known. Here we consider the class of polar graphs which are also cographs (graphs without induced path on four vertices). We provide a characterization in terms of forbidden subgraphs. Besides, we give an algorithm in time O(n) for finding a largest induced polar subgraph in cographs; this also serves as a polar cograph recognition algorithm. We examine also the monopolar cographs which are the (s,k)-polar cographs where min(s,k)?1. A characterization of these graphs by forbidden subgraphs is given. Some open questions related to polarity are discussed.     

Specifying periodic words by restrictions

Consider a periodic sequence over a finite alphabet, say ..ababab.... This sequence can be specified by prohibiting the subwords aa and bb. In the paper, the maximum period of a word that can be defined by using k restrictions is determined. A sharp exponential bound is obtained: the period of a word determined by k restrictions cannot exceed the kth Fibonacci number. Thus, the period colength is estimated. The problem is studied in the context of Gröbner bases, namely, the growth of a Gröbner basis of an ideal (the cogrowth of an algebra). The proof uses the technique of Rauzy graphs.     

New families of hypohamiltonian graphs

We construct three new infinite families of hypohamiltonian graphs having respectively 3k+1 vertices (k?3), 3k vertices (k?5) and 5k vertices (k?4); in particular, we exhibit a hypohamiltonian graph of order 19 and a cubic hypohamiltonian graph of order 20, the existence of which was still in doubt. Using these families, we get a lower bound for the number of non-isomorphic hypohamiltonian graphs of order 3k and 5k. We also give an example of an infinite graph G having no two-way infinite hamiltonian path, but in which every vertex-deleted subgraph G - x has such a path.     

Tough graphs and hamiltonian circuits

The toughness of a graph G is defined as the largest real number t such that deletion of any s points from G results in a graph which is either connected or else has at most s/t components. Clearly, every hamiltonian graph is 1-tough. Conversely, we conjecture that for some t₀, every t₀-tough graph is hamiltonian. Since a square of a k-connected graph is always k-tough, a proof of this conjecture with t₀ = 2 would imply Fleischner's theorem (the square of a block is hamiltonian). We construct an infinite family of ($\text{3}\text{2}$)-tough nonhamiltonian graphs.     

Planarity of iterated line graphs

The line index of a graph G is the smallest k such that the kth iterated line graph of G is nonplanar. We show that the line index of a graph is either infinite or it is at most 4. Moreover, we give a full characterization of all graphs with respect to their line index.     

Orientations of infinite graphs with prescribed edge-connectivity

We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.     

On low degree k-ordered graphs

A simple graph G is k-ordered (respectively, k-ordered hamiltonian) if, for any sequence of k distinct vertices v₁,…,v_k of G, there exists a cycle (respectively, a hamiltonian cycle) in G containing these k vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability, and motivated by the fact that k-orderedness of a graph implies (k-1)-connectivity, they posed the question of the existence of low degree k-ordered hamiltonian graphs. We construct an infinite family of graphs, which we call bracelet graphs, that are (k-1)-regular and are k-ordered hamiltonian for odd k. This result provides the best possible answer to the question of the existence of low degree k-ordered hamiltonian graphs for odd k. We further show that for even k, there exist no k-ordered bracelet graphs with minimum degree k-1 and maximum degree less than k+2, and we exhibit an infinite family of bracelet graphs with minimum degree k-1 and maximum degree k+2 that are k-ordered for even k. A concept related to k-orderedness, namely that of k-edge-orderedness, is likewise strongly related to connectivity properties. We study this relation and give bounds on the connectivity necessary to imply k-(edge-)orderedness properties.     

Polar cographs

A graph is (s, k)-polar if there exists a partition A, B of its vertex set such that A induces a complete s-partite graph and B a disjoint union of at most k cliques. Recognizing a polar graph is known to be NP-complete. Here we consider the class of polar graphs which are also cographs. We provide polynomial time algorithms and forbidden subgraphs characterizations for problems related to polar cographs.     

The capture time of a graph

We consider the game of Cops and Robbers played on finite and countably infinite connected graphs. The length of games is considered on cop-win graphs, leading to a new parameter, the capture time of a graph. While the capture time of a cop-win graph on n vertices is bounded above by n−3, half the number of vertices is sufficient for a large class of graphs including chordal graphs. Examples are given of cop-win graphs which have unique corners and have capture time within a small additive constant of the number of vertices. We consider the ratio of the capture time to the number of vertices, and extend this notion of capture time density to infinite graphs. For the infinite random graph, the capture time density can be any real number in [0,1]. We also consider the capture time when more than one cop is required to win. While the capture time can be calculated by a polynomial algorithm if the number k of cops is fixed, it is NP-complete to decide whether k cops can capture the robber in no more than t moves for every fixed t.     

Distance-balanced graphs: Symmetry conditions

A graph X is said to be distance-balanced if for any edge uv of X, the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. A graph X is said to be strongly distance-balanced if for any edge uv of X and any integer k, the number of vertices at distance k from u and at distance k+1 from v is equal to the number of vertices at distance k+1 from u and at distance k from v. Exploring the connection between symmetry properties of graphs and the metric property of being (strongly) distance-balanced is the main theme of this article. That a vertex-transitive graph is necessarily strongly distance-balanced and thus also distance-balanced is an easy observation. With only a slight relaxation of the transitivity condition, the situation changes drastically: there are infinite families of semisymmetric graphs (that is, graphs which are edge-transitive, but not vertex-transitive) which are distance-balanced, but there are also infinite families of semisymmetric graphs which are not distance-balanced. Results on the distance-balanced property in product graphs prove helpful in obtaining these constructions. Finally, a complete classification of strongly distance-balanced graphs is given for the following infinite families of generalized Petersen graphs: GP(n,2), GP(5k+1,k), GP(3k±3,k), and GP(2k+2,k).     

On infinite graphs with a specified number of colorings

In this paper we construct a planar graph of degree four which admits exactly N_u 3-colorings, we prove that such a graph must have degree at least four, and we consider various generalizations. We first allow our graph to have either one or two vertices of infinite degree and/or to admit only finitely many colorings and we note how this effects the degrees of the remaining vertices. We next consider n-colorings for n>3, and we construct graphs which we conjecture (but cannot prove) are of minimal degree. Finally, we consider nondenumerable graphs, and for every 3 <n<ω and every infinite cardinal k we construct a graph of cardinality k which admits exactly kn-colorings. We also show that the number of n-colorings of a denumerable graph can never be strictly between N_u and 2^N_u and that an appropriate generalization holds for at least certain nondenumerable graphs.     

An extension of Sallee’s theorem to infinite locally finite vap-free plane graphs

A graph isk-cyclable if givenk vertices there is a cycle that contains thek vertices. Sallee showed that every finite 3-connected planar graph is 5-cyclable. In this paper, by characterizing the circuit graphs and investigating the structure of LV-graphs, we extend his result to 3-connected infinite locally finite VAP-free plane graphs.     

On choosability of some complete multipartite graphs and Ohba's conjecture

A graph G is said to be chromatic-choosable if ch(G)=χ(G). Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba's conjecture is true if and only if it is true for complete multipartite graphs. But for complete multipartite graphs, the graphs for which Ohba's conjecture has been verified are nothing more than K_{3*2,2*(k-3),1}, K_3,2*(k-1), and K_{s+3,2*(k-s-1),1*s}. These results have been obtained indirectly from the investigation about complete multipartite graphs by Gravier and Maffray and by Enomoto et al. In this paper we show that Ohba's conjecture is true for complete multipartite graphs K_{4,3,2*(k-4),1*2} and K_{5,3,2*(k-5),1*3}. By the way, we give some discussions about a result of Enomoto et al.     

Polygon-circle and word-representable graphs

We describe work on the relationship between the independently-studied polygon-circle graphs and word-representable graphs.A graph G = (V, E) is word-representable if there exists a word w over the alpha-bet V such that letters x and y form a subword of the form xyxy ⋯ or yxyx ⋯ iff xy is an edge in E. Word-representable graphs generalise several well-known and well-studied classes of graphs [S. Kitaev, A Comprehensive Introduction to the Theory of Word-Representable Graphs, Lecture Notes in Computer Science 10396 (2017) 36–67; S. Kitaev, V. Lozin, “Words and Graphs”, Springer, 2015]. It is known that any word-representable graph is k-word-representable, that is, can be represented by a word having exactly k copies of each letter for some k dependent on the graph. Recognising whether a graph is word-representable is NP-complete ([S. Kitaev, V. Lozin, “Words and Graphs”, Springer, 2015, Theorem 4.2.15]). A polygon-circle graph (also known as a spider graph) is the intersection graph of a set of polygons inscribed in a circle [M. Koebe, On a new class of intersection graphs, Ann. Discrete Math. (1992) 141–143]. That is, two vertices of a graph are adjacent if their respective polygons have a non-empty intersection, and the set of polygons that correspond to vertices in this way are said to represent the graph. Recognising whether an input graph is a polygon-circle graph is NP-complete [M. Pergel, Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete, Graph-Theoretic Concepts in Computer Science: 33rd Int. Workshop, Lecture Notes in Computer Science, 4769 (2007) 238–247]. We show that neither of these two classes is included in the other one by showing that the word-representable Petersen graph and crown graphs are not polygon-circle, while the non-word-representable wheel graph W₅ is polygon-circle. We also provide a more refined result showing that for any k ≥ 3, there are k-word-representable graphs which are neither (k −1)-word-representable nor polygon-circle.     

On 3-regular 4-ordered graphs

A simple graph G is k-ordered (respectively, k-ordered hamiltonian), if for any sequence of k distinct vertices v₁,…,v_kof G there exists a cycle (respectively, hamiltonian cycle) in G containing these k vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability and posed the question of the existence of 3-regular 4-ordered (hamiltonian) graphs other than K₄ and K_3,3. Ng and Schultz observed that a 3-regular 4-ordered graph on more than 4 vertices is triangle free. We prove that a 3-regular 4-ordered graph G on more than 6 vertices is square free,and we show that the smallest graph that is triangle and square free, namely the Petersen graph, is 4-ordered. Furthermore, we prove that the smallest graph after K₄ and K_3,3 that is 3-regular 4-ordered hamiltonianis the Heawood graph. Finally, we construct an infinite family of 3-regular 4-ordered graphs.     

q-Coverings,codes, and line graphs

In this paper we consider the relationship between q-coverings of a regular graph and perfect 1-codes in line graphs. An infinite class of perfect 1-codes in the line graphs L(I_k) is constructed.     

Graphs with the maximum or minimum number of 1-factors

Recently Alon and Friedland have shown that graphs which are the union of complete regular bipartite graphs have the maximum number of 1-factors over all graphs with the same degree sequence. We identify two families of graphs that have the maximum number of 1-factors over all graphs with the same number of vertices and edges: the almost regular graphs which are unions of complete regular bipartite graphs, and complete graphs with a matching removed. The first family is determined using the Alon and Friedland bound. For the second family, we show that a graph transformation which is known to increase network reliability also increases the number of 1-factors. In fact, more is true: this graph transformation increases the number of k-factors for all k≥1, and “in reverse” also shows that in general, threshold graphs have the fewest k-factors. We are then able to determine precisely which threshold graphs have the fewest 1-factors. We conjecture that the same graphs have the fewest k-factors for all k≥2 as well.     

Altitude of regular graphs with girth at least five

The altitude of a graph G is the largest integer k such that for each linear ordering f of its edges, G has a (simple) path P of length k for which f increases along the edge sequence of P. We determine a necessary and sufficient condition for cubic graphs with girth at least five to have altitude three and show that for r?4, r-regular graphs with girth at least five have altitude at least four. Using this result we show that some snarks, including all but one of the Blanus?a type snarks, have altitude three while others, including the flower snarks, have altitude four. We construct an infinite class of 4-regular graphs with altitude four.     

Uniquely pairable graphs

The concept of a k-pairable graph was introduced by Z. Chen [On k-pairable graphs, Discrete Mathematics 287 (2004), 11-15] as an extension of hypercubes and graphs with an antipodal isomorphism. In the present paper we generalize further this concept of a k-pairable graph to the concept of a semi-pairable graph. We prove that a graph is semi-pairable if and only if its prime factor decomposition contains a semi-pairable prime factor or some repeated prime factors. We also introduce a special class of k-pairable graphs which are called uniquely k-pairable graphs. We show that a graph is uniquely pairable if and only if its prime factor decomposition has at least one pairable prime factor, each prime factor is either uniquely pairable or not semi-pairable, and all prime factors which are not semi-pairable are pairwise non-isomorphic. As a corollary we give a characterization of uniquely pairable Cartesian product graphs.     

Properties of Groups for the Cage and Degree/Diameter Problems

A (k, g)-cage is a k-regular graph of girth g of minimum order. While many of the best known constructions of small k-regular graphs of girth g are known to be Cayley graphs, no general theory of the relation between the girth of a Cayley graph and the structure of the underlying group has been developed. We attempt to fill the gap by focusing on the girths of Caley graphs of nilpotent and solvable groups, and present a series of results supporting the intuitive idea that the closer a group is to being abelian, the less suitable it is for constructing Cayley graphs of large girths. Specifically, we establish the existence of upper bounds on the girths of Cayley graphs with respect to the nilpotency class and/or the length of the derived sequence of the underlying groups.