Hamiltonian Type Properties in Claw-Free $$P_5$$-Free Graphs

A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each integer r in the set \(\{ m, m + 1, \ldots , n \}\). This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree et al. in (Graphs Combin 20:291–310, 2004). The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. Broersma and Veldman showed in (Contemporary methods in graph theory, BI-Wiss.-Verlag, Mannheim, Wien, Zürich, pp 181–194, 1990) that any 2-connected claw-free \(P_5\)-free graph must be hamiltonian. In fact, every non-hamiltonian cycle in such a graph is either extendable or very dense. We show that any 2-connected claw-free \(P_5\)-free graph is (k, 3k)-pancyclic for each integer \(k \ge 2\). We also show that such a graph is (1, 5)-pancyclic. Examples are provided which show that these results are best possible. Each example we provide represents an infinite family of graphs.     

Sharpening an Ore-type version of the Corrádi–Hajnal theorem

Corrádi and Hajnal (Acta Math Acad Sci Hung 14:423–439, 1963) proved that for all \(k\ge 1\) and \(n\ge 3k\), every (simple) graph G on n vertices with minimum degree \(\delta (G)\ge 2k\) contains k disjoint cycles. The degree bound is sharp. Enomoto and Wang proved the following Ore-type refinement of the Corrádi–Hajnal theorem: For all \(k\ge 1\) and \(n\ge 3k\), every graph G on n vertices contains k disjoint cycles, provided that \(d(x)+d(y)\ge 4k-1\) for all distinct nonadjacent vertices x, y. Very recently, it was refined for \(k\ge 3\) and \(n\ge 3k+1\): If G is a graph on n vertices such that \(d(x)+d(y)\ge 4k-3\) for all distinct nonadjacent vertices x, y, then G has k vertex-disjoint cycles if and only if the independence number \(\alpha (G)\le n-2k\) and G is not one of two small exceptions in the case \(k=3\). But the most difficult case, \(n=3k\), was not handled. In this case, there are more exceptional graphs, the statement is more sophisticated, and some of the proofs do not work. In this paper we resolve this difficult case and obtain the full picture of extremal graphs for the Ore-type version of the Corrádi–Hajnal theorem. Since any k disjoint cycles in a 3k-vertex graph G must be 3-cycles, the existence of such k cycles is equivalent to the existence of an equitable k-coloring of the complement of G. Our proof uses the language of equitable colorings, and our result can be also considered as an Ore-type version of a partial case of the Chen–Lih–Wu Conjecture on equitable colorings.     

Coloring of the Square of Kneser Graph $$$$

The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n elements set, with two vertices adjacent if they are disjoint. The square \(G^2\) of a graph G is the graph defined on V(G) such that two vertices u and v are adjacent in \(G^2\) if the distance between u and v in G is at most 2. Determining the chromatic number of the square of the Kneser graph K(n, k) is an interesting graph coloring problem, and is also related with intersecting family problem. The square of K(2k, k) is a perfect matching and the square of K(n, k) is the complete graph when \(n \ge 3k-1\). Hence coloring of the square of \(K(2k +1, k)\) has been studied as the first nontrivial case. In this paper, we focus on the question of determining \(\chi (K^2(2k+r,k))\) for \(r \ge 2\). Recently, Kim and Park (Discrete Math 315:69–74, 2014) showed that \(\chi (K^2(2k+1,k)) \le 2k+2\) if \( 2k +1 = 2^t -1\) for some positive integer t. In this paper, we generalize the result by showing that for any integer r with \(1 \le r \le k -2\),

1. (a)
   \(\chi (K^2 (2k+r, k)) \le (2k+r)^r\),   if   \(2k + r = 2^t\) for some integer t, and
    
2. (b)
   \(\chi (K^2 (2k+r, k)) \le (2k+r+1)^r\),   if  \(2k + r = 2^t-1\) for some integer t.
    

On the other hand, it was shown in Kim and Park (Discrete Math 315:69–74, 2014) that \(\chi (K^2 (2k+r, k)) \le (r+2)(3k + \frac{3r+3}{2})^r\) for \(2 \le r \le k-2\). We improve these bounds by showing that for any integer r with \(2 \le r \le k -2\), we have \(\chi (K^2 (2k+r, k)) \le 2 \left( \frac{9}{4}k + \frac{9(r+3)}{8} \right) ^r\). Our approach is also related with injective coloring and coloring of Johnson graph.

     

A variation of a conjecture due to Erdös and Sós

Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.     

Extendability of Contractible Configurations for Nowhere-Zero Flows and Modulo Orientations

Let H be a connected graph and G be a supergraph of H. It is trivial that for any k-flow (D, f) of G, the restriction of (D, f) on the edge subset E(G / H) is a k-flow of the contracted graph G / H. However, the other direction of the question is neither trivial nor straightforward at all: for any k-flow \((D',f')\) of the contracted graph G / H, whether or not the supergraph G admits a k-flow (D, f) that is consistent with \((D',f')\) in the edge subset E(G / H). In this paper, we will investigate contractible configurations and their extendability for integer flows, group flows, and modulo orientations. We show that no integer flow contractible graphs are extension consistent while some group flow contractible graphs are also extension consistent. We also show that every modulo \((2k+1)\)-orientation contractible configuration is also extension consistent and there are no modulo (2k)-orientation contractible graphs.     

<Emphasis Type="Italic">s</Emphasis>-Vertex Pancyclic Index

A graph G is vertex pancyclic if for each vertex \({v \in V(G)}\) , and for each integer k with 3 ≤ k ≤ |V(G)|, G has a k-cycle C _k such that \({v \in V(C_k)}\) . Let s ≥ 0 be an integer. If the removal of at most s vertices in G results in a vertex pancyclic graph, we say G is an s-vertex pancyclic graph. Let G be a simple connected graph that is not a path, cycle or K _1,3. Let l(G) = max{m : G has a divalent path of length m that is not both of length 2 and in a K ₃}, where a divalent path in G is a path whose interval vertices have degree two in G. The s-vertex pancyclic index of G, written vp _s (G), is the least nonnegative integer m such that L ^m (G) is s-vertex pancyclic. We show that for a given integer s ≥ 0,

$vp_s(G)\le \left\{\begin{array}{l@{\quad}l}\qquad\quad\quad\,\,\,\,\,\,\, l(G)+s+1: \quad {\rm if} \,\, 0 \le s \le 4 \\ l(G)+\lceil {\rm log}_2(s-2) \rceil+4: \quad {\rm if} \,\, s \ge 5 \end{array}\right.$

And we improve the bound for essentially 3-edge-connected graphs. The lower bound and whether the upper bound is sharp are also discussed.

     

Minimum Difference Representations of Graphs

Define a k-minimum-difference-representation (k-MDR) of a graph G to be a family of sets \({\{S(v): v\in V(G)\}}\) such that u and v are adjacent in G if and only if min{|S(u)?S(v)|, |S(v)?S(u)|} ≥ k. Define ρ _min(G) to be the smallest k for which G has a k-MDR. In this note, we show that {ρ _min(G)} is unbounded. In particular, we prove that for every k there is an n ₀ such that for n > n ₀ ‘almost all’ graphs of order n satisfy ρ _min(G) > k. As our main tool, we prove a Ramsey-type result on traces of hypergraphs.     

An implicit degree condition for relative length of long paths and cycles in graphs

For a graph G, we denote by p(G) and c(G) the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id(v) denotes the implicit degree of v. In this paper, we obtain that if G is a 2-connected graph on n vertices such that the implicit degree sum of any three independent vertices is at least n + 1, then either G contains a hamiltonian path, or c(G) ≥ p(G) ? 1.     

On the automorphism group of the Aschbacher graph

A Moore graph is a regular graph of degree k and diameter d with v vertices such that v ≤ 1 + k + k(k ? 1) + ... + k(k ? 1)^d?1. It is known that a Moore graph of degree k ≥ 3 has diameter 2; i.e., it is strongly regular with parameters λ = 0, µ = 1, and v = k ² + 1, where the degree k is equal to 3, 7, or 57. It is unknown whether there exists a Moore graph of degree k = 57. Aschbacher showed that a Moore graph with k = 57 is not a graph of rank 3. In this connection, we call a Moore graph with k = 57 the Aschbacher graph and investigate its automorphism group G without additional assumptions (earlier, it was assumed that G contains an involution).     

Complexities of normal bases constructed from Gauss periods

Let q be a power of a prime p, and let \(r=nk+1\) be a prime such that \(r\not \mid q\), where n and k are positive integers. Under a simple condition on q, r and k, a Gauss period of type (n, k) is a normal element of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\); the complexity of the resulting normal basis of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\) is denoted by C(n, k; p). Recent works determined C(n, k; p) for \(k\le 7\) and all qualified n and q. In this paper, we show that for any given \(k>0\), C(n, k; p) is given by an explicit formula except for finitely many primes \(r=nk+1\) and the exceptional primes are easily determined. Moreover, we describe an algorithm that allows one to compute C(n, k; p) for the exceptional primes \(r=nk+1\). Our numerical results cover C(n, k; p) for \(k\le 20\) and all qualified n and q.     

Building Graphs Whose Independence Polynomials Have Only Real Roots

A stable set in a graph G is a set of pairwise non-adjacent vertices, and the stability number α(G) is the maximum size of a stable set in G. The independence polynomial of G is

$I(G; x) = s_{0}+s_{1}x+s_{2}x^{2}+\cdots+s_{\alpha}x^{\alpha},\alpha=\alpha(G),$

where s _k equals the number of stable sets of cardinality k in G (Gutman and Harary [11]).

Unlike the matching polynomial, the independence polynomial of a graph can have non-real roots. It is known that the polynomial I(G; x) has only real roots whenever (a) α(G) = 2 (Brown et al. [4]), (b) G is claw-free (Chudnowsky and Symour [6]). Brown et al. [3] proved that given a well-covered graph G, one can define a well-covered graph H such that G is a subgraph of H, α(G) = α(H), and I(H; x) has all its roots simple and real.In this paper, we show that starting from a graph G whose I(G; x) has only real roots, one can build an infinite family of graphs, some being well-covered, whose independence polynomials have only real roots (and, sometimes, are also palindromic).     

Note on a conjecture for the sum of signless Laplacian eigenvalues

For a simple graph G on n vertices and an integer k with 1 ? k ? n, denote by \(\mathcal{S}^+_k\) (G) the sum of k largest signless Laplacian eigenvalues of G. It was conjectured that \(\mathcal{S}^+_k(G)\leqslant{e}(G)+(^{k+1}_{\;\;2})\) (G) ? e(G) + (k+1 2), where e(G) is the number of edges of G. This conjecture has been proved to be true for all graphs when k ∈ {1, 2, n ? 1, n}, and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all k). In this note, this conjecture is proved to be true for all graphs when k = n ? 2, and for some new classes of graphs.     

Normal coverings of solvable groups

For a finite non cyclic group G, let γ(G) be the smallest integer k such that G contains k proper subgroups H ₁, . . . , H _k with the property that every element of G is contained in \({H_i^g}\) for some \({i \in \{1,\dots,k\}}\) and \({g \in G.}\) We prove that for every n ≥ 2, there exists a finite solvable group G with γ(G) = n.     

Token Graphs

For a graph G and integer k ≥ 1, we define the token graph F _k (G) to be the graph with vertex set all k-subsets of V(G), where two vertices are adjacent in F _k (G) whenever their symmetric difference is a pair of adjacent vertices in G. Thus vertices of F _k (G) correspond to configurations of k indistinguishable tokens placed at distinct vertices of G, where two configurations are adjacent whenever one configuration can be reached from the other by moving one token along an edge from its current position to an unoccupied vertex. This paper introduces token graphs and studies some of their properties including: connectivity, diameter, cliques, chromatic number, Hamiltonian paths, and Cartesian products of token graphs.     

Fair 1-Factorizations and Fair Holey 1-Factorizations of Complete Multipartite Graphs

A k-factor of a graph G is a k-regular spanning subgraph of G. A k-factorization is a partition of E(G) into k-factors. Let K(n, p) be the complete multipartite graph with p parts, each of size n. If \(V_{1},\ldots , V_{p}\) are the p parts of V(K(n, p)), then a holey k -factor of deficiency \(V_{i}\) of K(n, p) is a k-factor of \(K(n,p)-V_{i}\) for some i satisfying \(1\le i \le p\). Hence a holey k -factorization is a set of holey k-factors whose edges partition E(K(n, p)). Representing each (holey) k-factor as a color class in an edge-coloring, a (holey) k-factorization of K(n, p) is said to be fair if between each pair of parts the color classes have size within one of each other (so the edges are shared “evenly” among the permitted (holey) factors). In this paper the existence of fair 1-factorizations of K(n, p) is completely settled, as is the existence of fair holey 1-factorizations of K(n, p). The latter result can be used to provide a new construction for symmetric quasigroups of order np with holes of size n. Such quasigroups have the additional property that the permitted symbols are shared as evenly as possible among the cells in each \(n \times n\) “box”. These quasigroups are in some sense as far from frames produced by direct products as possible.     

Edge clique covering sum of graphs

The edge clique cover sum number (resp. edge clique partition sum number) of a graph G, denoted by scc(G) (resp. scp(G)), is defined as the smallest integer k for which there exists a collection of complete subgraphs of G, covering (resp. partitioning) all edges of G such that the sum of sizes of the cliques is at most k. By definition, scc(G) \({\leqq}\) scp(G). Also, it is known that for every graph G on n vertices, scp(G) \({\leqq n^{2}/2}\). In this paper, among some other results, we improve this bound for scc(G). In particular, we prove that if G is a graph on n vertices with no isolated vertex and the maximum degree of the complement of G is d ? 1, for some integer d, then scc(G) \({\leqq cnd\left\lceil\log \left(({n-1})/(d-1)\right)\right\rceil}\), where c is a constant. Moreover, we conjecture that this bound is best possible up to a constant factor. Using a well-known result by Bollobás on set systems, we prove that this conjecture is true at least for d = 2. Finally, we give an interpretation of this conjecture as an interesting set system problem which can be viewed as a multipartite generalization of Bollobás’ two families theorem.     

Degree conditions restricted to induced paths for hamiltonicity of claw-heavy graphs

Broersma and Veldman proved that every 2-connected claw-free and P ₆-free graph is hamiltonian. Chen et al. extended this result by proving every 2-connected claw-heavy and P ₆-free graph is hamiltonian. On the other hand, Li et al. constructed a class of 2-connected graphs which are claw-heavy and P ₆-o-heavy but not hamiltonian. In this paper, we further give some Ore-type degree conditions restricting to induced copies of P ₆ of a 2-connected claw-heavy graph that can guarantee the graph to be hamiltonian. This improves some previous related results.     

Proof of the bandwidth conjecture of Bollobás and Komlós

In this paper we prove the following conjecture by Bollobás and Komlós: For every γ > 0 and integers r ≥ 1 and Δ, there exists β > 0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least ((r ? 1)/r + γ)n and H is an r-chromatic graph with n vertices, bandwidth at most β n and maximum degree at most Δ, then G contains a copy of H.     

Conditional connectivity of bubble sort graphs

A subset F ? V (G) is called an R ^k -vertex-cut of a graph G if G ? F is disconnected and each vertex of G ? F has at least k neighbors in G ? F. The R ^k -vertex-connectivity of G, denoted by κ ^k (G), is the cardinality of a minimum R ^k -vertex-cut of G. Let B _n be the bubble sort graph of dimension n. It is known that κ _k (B _n ) = 2 ^k (n ? k ? 1) for n ≥ 2k and k = 1, 2. In this paper, we prove it for k = 3 and conjecture that it is true for all k ∈ N. We also prove that the connectivity cannot be more than conjectured.     

Neighbor sum distinguishing colorings of graphs with maximum average degree less than $$\tfrac{{37}} {{12}}$$

Let G be a graph and let its maximum degree and maximum average degree be denoted by Δ(G) and mad(G), respectively. A neighbor sum distinguishing k-edge colorings of graph G is a proper k-edge coloring of graph G such that, for any edge uv ∈ E(G), the sum of colors assigned on incident edges of u is different from the sum of colors assigned on incident edges of v. The smallest value of k in such a coloring of G is denoted by χ′_∑(G). Flandrin et al. proposed the following conjecture that χ′_∑ (G) ≤ Δ(G) + 2 for any connected graph with at least 3 vertices and G ≠ C₅. In this paper, we prove that the conjecture holds for a normal graph with mad(G) < \(\tfrac{{37}}{{12}}\) and Δ(G) ≥ 7.