More odd graph theory from another point of view

The Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of $\left[n\right]=\{1,2,\dots ,n\}$ and an edge between any two vertices that are disjoint. If $n=2k+1$, then $K(n,k)$ is called an odd graph. Let $n>4$ and $1<k<\frac{n}{2}$. In the present paper, we show that if the Kneser graph $K(n,k)$ is of even order where $n$ is an odd integer or both of the integers $n,k$ are even, then $K(n,k)$ is a vertex-transitive non Cayley graph. Although, these are special cases of Godsil [7], unlike his proof that uses some very deep group-theoretical facts, ours uses no heavy group-theoretic facts. We obtain our results by using some rather elementary facts of number theory and group theory. We show that ‘almost all’ odd graphs are of even order, and consequently are vertex-transitive non Cayley graphs. Finally, we show that if $k>4$ is an even integer such that $k$ is not of the form $k=2^t$ for some $t>2$, then the line graph of the odd graph $O_{k+1}$ is a vertex-transitive non Cayley graph.     

On the distance between linear codes

Let V be an n-dimensional vector space over the finite field consisting of q elements and let ${\mathrm{\Gamma }}_k(V)$ be the Grassmann graph formed by k-dimensional subspaces of V, $1<k<n-1$. Denote by $\mathrm{\Gamma }{(n,k)}_q$ the restriction of ${\mathrm{\Gamma }}_k(V)$ to the set of all non-degenerate linear ${[n,k]}_q$ codes. We show that for any two codes the distance in $\mathrm{\Gamma }{(n,k)}_q$ coincides with the distance in ${\mathrm{\Gamma }}_k(V)$ only in the case when $n<{(q+1)}^2+k-2$, i.e. if n is sufficiently large then for some pairs of codes the distances in the graphs ${\mathrm{\Gamma }}_k(V)$ and $\mathrm{\Gamma }{(n,k)}_q$ are distinct. We describe one class of such pairs.     

Rainbow number of matchings in planar graphs

The rainbow number$rb(G,H)$ for the graph $H$ in $G$ is defined to be the minimum integer $c$ such that any $c$-edge-coloring of $G$ contains a rainbow $H$. As one of the most important structures in graphs, the rainbow number of matchings has drawn much attention and has been extensively studied. Jendrol et al. initiated the rainbow number of matchings in planar graphs and they obtained bounds for the rainbow number of the matching $k{K}_2$ in the plane triangulations, where the gap between the lower and upper bounds is $O\left(k^3\right)$. In this paper, we show that the rainbow number of the matching $k{K}_2$ in maximal outerplanar graphs of order $n$ is $n+O\left(k\right)$. Using this technique, we show that the rainbow number of the matching $k{K}_2$ in some subfamilies of plane triangulations of order $n$ is $2n+O\left(k\right)$. The gaps between our lower and upper bounds are only $O\left(k\right)$.     

A new approach to the chromatic number of the square of Kneser graph K(2k+1,k)

The vertices of Kneser graph $K(n,k)$ are the subsets of $\{1,2,\dots ,n\}$ of cardinality $k$, two vertices are adjacent if and only if they are disjoint. The square $G^2$ of a graph $G$ is defined on the vertex set of $G$ with two vertices adjacent if their distance in $G$ is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when $n=2k+1$. It is believed that $\chi \left(K^2(2k+1,k)\right)=2k+c$ where $c$ is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: $8k∕3+20∕3$ for 1$k\ge 3$ (Kim and Park, 2014) and $32k∕15+32$ for $k\ge 7$ (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to $\chi \left(K^2(2k+1,k)\right)\le 5k∕2+c$, where $c$ is a constant in $\{5∕2,9∕2,5,6\}$, depending on $k\ge 2$.     

Extremal problems on the Hamiltonicity of claw-free graphs

In 1962, Erd?s proved that if a graph $G$ with $n$ vertices satisfies

$e\left(G\right)>max\left\{\left(\genfrac{}{}{0ex}{}{n?k}{2}\right)+k^2,\left(\genfrac{}{}{0ex}{}{?(n+1)∕2?}{2}\right)+{?\frac{n?1}{2}?}^2\right\},$

where the minimum degree $\delta \left(G\right)\ge k$ and $1\le k\le (n?1)∕2$, then it is Hamiltonian. For $n\ge 2k+1$, let $E_n^k=K_k\vee (k{K}_1+K_{n?2k})$, where “$\vee$” is the “join” operation. One can observe $e\left(E_n^k\right)=\left(\genfrac{}{}{0ex}{}{n?k}{2}\right)+k^2$ and $E_n^k$ is not Hamiltonian. As $E_n^k$ contains induced claws for $k\ge 2$, a natural question is to characterize all 2-connected claw-free non-Hamiltonian graphs with the largest possible number of edges. We answer this question completely by proving a claw-free analog of Erd?s’ theorem. Moreover, as byproducts, we establish several tight spectral conditions for a 2-connected claw-free graph to be Hamiltonian. Similar results for the traceability of connected claw-free graphs are also obtained. Our tools include Ryjá?ek’s claw-free closure theory and Brousek’s characterization of minimal 2-connected claw-free non-Hamiltonian graphs.     

Stability in the Erdős–Gallai Theorem on cycles and paths,II

The Erd?s–Gallai Theorem states that for $k\ge 3$, any $n$-vertex graph with no cycle of length at least $k$ has at most $\frac{1}{2}(k?1)(n?1)$ edges. A stronger version of the Erd?s–Gallai Theorem was given by Kopylov: If $G$ is a 2-connected $n$-vertex graph with no cycle of length at least $k$, then $e\left(G\right)\le max\{h(n,k,2),h(n,k,?\frac{k?1}{2}?)\}$, where $h(n,k,a)?\left(\genfrac{}{}{0ex}{}{k?a}{2}\right)+a(n?k+a)$. Furthermore, Kopylov presented the two possible extremal graphs, one with $h(n,k,2)$ edges and one with $h(n,k,?\frac{k?1}{2}?)$ edges.In this paper, we complete a stability theorem which strengthens Kopylov’s result. In particular, we show that for $k\ge 3$ odd and all $n\ge k$, every $n$-vertex 2-connected graph $G$ with no cycle of length at least $k$ is a subgraph of one of the two extremal graphs or $e\left(G\right)\le max\{h(n,k,3),h(n,k,\frac{k?3}{2})\}$. The upper bound for $e\left(G\right)$ here is tight.     

Defective 2-colorings of planar graphs without 4-cycles and 5-cycles

A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define $V_i?\{v\in V\left(G\right):c\left(v\right)=i\}$ for $i=1$ and $2.$ We say that $G$ is $(d_1,d_2)$-colorable if $G$ has a 2-coloring such that $V_i$ is an empty set or the induced subgraph $G\left[V_i\right]$ has the maximum degree at most $d_i$ for $i=1$ and $2.$ Let $G$ be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether $G$ is $(0,k)$-colorable is NP-complete for every positive integer $k.$ Moreover, we construct non-$(1,k)$-colorable planar graphs without 4-cycles and 5-cycles for every positive integer $k.$ In contrast, we prove that $G$ is $(d_1,d_2)$-colorable where $(d_1,d_2)=(4,4),(3,5),$ and $(2,9).$     

Steiner tree packing number and tree connectivity

Let $S$ be a set of at least two vertices in a graph $G$. A subtree $T$ of $G$ is a $S$-Steiner tree if $S?V\left(T\right)$. Two $S$-Steiner trees $T_1$ and $T_2$ are edge-disjoint (resp. internally vertex-disjoint) if $E\left(T_1\right)\cap E\left(T_2\right)=?$ (resp. $E\left(T_1\right)\cap E\left(T_2\right)=?$ and $V\left(T_1\right)\cap V\left(T_2\right)=S$). Let ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) $S$-Steiner trees in $G$, and let ${\lambda }_k\left(G\right)$ (resp. ${\kappa }_k\left(G\right)$) be the minimum ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) for $S$ ranges over all $k$-subset of $V\left(G\right)$. Kriesell conjectured that if ${\lambda }_G\left(\{x,y\}\right)\ge 2k$ for any $x,y\in S$, then ${\lambda }_G\left(S\right)\ge k$. He proved that the conjecture holds for $\left|S\right|=3,4$. In this paper, we give a short proof of Kriesell’s Conjecture for $\left|S\right|=3,4$, and also show that ${\lambda }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ (resp. ${\kappa }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ ) if $\lambda \left(G\right)\ge ?$ (resp. $\kappa \left(G\right)\ge ?$) in $G$, where $k=3,4$. Moreover, we also study the relation between ${\kappa }_k\left(L\left(G\right)\right)$ and ${\lambda }_k\left(G\right)$, where $L\left(G\right)$ is the line graph of $G$.     

Sparse graphs of girth at least five are packable

A graph is packable if it is a subgraph of its complement. The following statement was conjectured by Faudree, Rousseau, Schelp and Schuster in 1981: every non-star graph $G$ with girth at least $5$ is packable.The conjecture was proved by Faudree et al. with the additional condition that $G$ has at most $\frac{6}{5}n?2$ edges. In this paper, for each integer $k\ge 3$, we prove that every non-star graph with girth at least $5$ and at most $\frac{2k?1}{k}n?{\alpha }_k\left(n\right)$ edges is packable, where ${\alpha }_k\left(n\right)$ is $o\left(n\right)$ for every $k$. This implies that the conjecture is true for sufficiently large planar graphs.     

Turán numbers of vertex-disjoint cliques in r-partite graphs

For two graphs $G$ and $H$, the Turán number$ex(G,H)$ is the maximum number of edges in a subgraph of $G$ that contains no copy of $H$. Chen, Li, and Tu determined the Turán numbers $ex(K_{m,n},k{K}_2)$ for all $k\ge 1$ Chen et al. (2009). In this paper we will determine the Turán numbers $ex(K_{a_1,\dots ,a_r},k{K}_r)$ for all $r\ge 3$ and $k\ge 1$.     

A stability version for a theorem of Erdős on nonhamiltonian graphs

Let $n,d$ be integers with $1\le d\le ?\frac{n?1}{2}?$, and set $h(n,d)?\left(\genfrac{}{}{0ex}{}{n?d}{2}\right)+d^2$ and $e(n,d)?max\{h(n,d),h(n,?\frac{n?1}{2}?)\}$. Because $h(n,d)$ is quadratic in $d$, there exists a $d_0\left(n\right)=(n∕6)+O\left(1\right)$ such that

$e(n,1)>e(n,2)>?>e(n,d_0)=e(n,d_0+1)=?=e\left(n,?\frac{n?1}{2}?\right).$

A theorem by Erd?s states that for $d\le ?\frac{n?1}{2}?$, any $n$-vertex nonhamiltonian graph $G$ with minimum degree $\delta \left(G\right)\ge d$ has at most $e(n,d)$ edges, and for $d>d_0\left(n\right)$ the unique sharpness example is simply the graph $K_n?E\left(K_{?(n+1)∕2?}\right)$. Erd?s also presented a sharpness example $H_{n,d}$ for each $1\le d\le d_0\left(n\right)$.We show that if $d<d_0\left(n\right)$ and a $2$-connected, nonhamiltonian $n$-vertex graph $G$ with $\delta \left(G\right)\ge d$ has more than $e(n,d+1)$ edges, then $G$ is a subgraph of $H_{n,d}$. Note that $e(n,d)?e(n,d+1)=n?3d?2\ge n∕2$ whenever $d<d_0\left(n\right)?1$.     

Bounds on the length of a game of Cops and Robbers

In the game of Cops and Robbers, a team of cops attempts to capture a robber on a graph $G$. All players occupy vertices of $G$. The game operates in rounds; in each round the cops move to neighboring vertices, after which the robber does the same. The minimum number of cops needed to guarantee capture of a robber on $G$ is the cop number of $G$, denoted $c\left(G\right)$, and the minimum number of rounds needed for them to do so is the capture time. It has long been known that the capture time of an $n$-vertex graph with cop number $k$ is $O\left(n^{k+1}\right)$. More recently, Bonato et al. (2009) and Gaven?iak (2010) showed that for $k=1$, this upper bound is not asymptotically tight: for graphs with cop number 1, the cop can always win within $n?4$ rounds. In this paper, we show that the upper bound is tight when $k\ge 2$: for fixed $k\ge 2$, we construct arbitrarily large graphs $G$ having capture time at least ${\left(\frac{\left|V\left(G\right)\right|}{40k^4}\right)}^{k+1}$.In the process of proving our main result, we establish results that may be of independent interest. In particular, we show that the problem of deciding whether $k$ cops can capture a robber on a directed graph is polynomial-time equivalent to deciding whether $k$ cops can capture a robber on an undirected graph. As a corollary of this fact, we obtain a relatively short proof of a major conjecture of Goldstein and Reingold (1995), which was recently proved through other means (Kinnersley, 2015). We also show that $n$-vertex strongly-connected directed graphs with cop number 1 can have capture time $\Omega \left(n^2\right)$, thereby showing that the result of Bonato et al. (2009) does not extend to the directed setting.     

On the spanning connectivity of the generalized Petersen graphs P(n,3)

In this paper, we employed lattice model to describe the three internally vertex-disjoint paths that span the vertex set of the generalized Petersen graph $P(n,3)$. We showed that the $P(n,3)$ is 3-spanning connected for odd $n$. Based on the lattice model, five amalgamated and one extension mechanisms are introduced to recursively establish the 3-spanning connectivity of the $P(n,3)$. In each amalgamated mechanism, a particular lattice trail was amalgamated with the lattice trails that was dismembered, transferred, or extended from parts of the lattice trails for $P(n?6,3)$, where a lattice tail is a trail in the lattice model that represents a path in $P(n,3)$.