Estimates on the size of the cycle spectra of Hamiltonian graphs

Given a graph $G$, let $S\left(G\right)$ be the set of all cycle lengths contained in $G$ and let $s\left(G\right)=\left|S\left(G\right)\right|$. Let $?\left(G\right)=\{3,\dots ,n\}?S\left(G\right)$ and let $d$ be the greatest common divisor of $n?2$ and all the positive pairwise differences of elements in $?\left(G\right)$. We prove that if a Hamiltonian graph $G$ of order $n$ has at least $\frac{n(p+2)}{4}+1$ edges, where $p$ is an integer such that $1\le p\le n?2$, then $s\left(G\right)\ge p$ or $G$ is exceptional, by which we mean $d?(??2)$ for some $?\in ?\left(G\right)$. We also discuss cases where $G$ is not exceptional, for example when $n?2$ is prime. Moreover, we show that $s\left(G\right)\ge min\{p,\frac{n?3}{2}\}$, which if $G$ is bipartite implies that $s\left(G\right)\ge min\{?\frac{4(m?1)}{n}?2?,\frac{n?2}{2}\}$, where $m$ is the number of edges in $G$.     

On 3-stable number conditions in n-connected claw-free graphs

For a subgraph $X$ of $G$, let ${\alpha }_G^3\left(X\right)$ be the maximum number of vertices of $X$ that are pairwise distance at least three in $G$. In this paper, we prove three theorems. Let $n$ be a positive integer, and let $H$ be a subgraph of an $n$-connected claw-free graph $G$. We prove that if $n\ge 2$, then either $H$ can be covered by a cycle in $G$, or there exists a cycle $C$ in $G$ such that ${\alpha }_G^3(H?V\left(C\right))\le {\alpha }_G^3\left(H\right)?n$. This result generalizes the result of Broersma and Lu that $G$ has a cycle covering all the vertices of $H$ if ${\alpha }_G^3\left(H\right)\le n$. We also prove that if $n\ge 1$, then either $H$ can be covered by a path in $G$, or there exists a path $P$ in $G$ such that ${\alpha }_G^3(H?V\left(P\right))\le {\alpha }_G^3\left(H\right)?n?1$. By using the second result, we prove the third result. For a tree $T$, a vertex of $T$ with degree one is called a leaf of $T$. For an integer $k\ge 2$, a tree which has at most $k$ leaves is called a $k$-ended tree. We prove that if ${\alpha }_G^3\left(H\right)\le n+k?1$, then $G$ has a $k$-ended tree covering all the vertices of $H$. This result gives a positive answer to the conjecture proposed by Kano et al. (2012).     

Turán number and decomposition number of intersecting odd cycles

Given a graph $H$, the Turán function $\mathrm{ex}(n,H)$ is the maximum number of edges in a graph on $n$ vertices that does not contain $H$ as a subgraph. Let $s,t$ be integers and let $H_{s,t}$ be a graph consisting of $s$ triangles and $t$ cycles of odd lengths at least 5 which intersect in exactly one common vertex. Erd?s et al. (1995) determined the Turán function $\mathrm{ex}(n,H_{s,0})$ and the corresponding extremal graphs. Recently, Hou et al. (2016) determined $\mathrm{ex}(n,H_{0,t})$ and the extremal graphs, where the $t$ cycles have the same odd length $q$ with $q?5$. In this paper, we further determine $\mathrm{ex}(n,H_{s,t})$ and the extremal graphs, where $s?0$ and $t?1$. Let $?(n,H)$ be the smallest integer such that, for all graphs $G$ on $n$ vertices, the edge set $E\left(G\right)$ can be partitioned into at most $?(n,H)$ parts, of which every part either is a single edge or forms a graph isomorphic to $H$. Pikhurko and Sousa conjectured that $?(n,H)=\mathrm{ex}(n,H)$ for $\chi \left(H\right)?3$ and all sufficiently large $n$. Liu and Sousa (2015) verified the conjecture for $H_{s,0}$. In this paper, we further verify Pikhurko and Sousa’s conjecture for $H_{s,t}$ with $s?0$ and $t?1$.     

Which cospectral graphs have same degree sequences

Two graphs are said to be $L$-cospectral (respectively, $Q$-cospectral) if they have the same (respectively, signless) Laplacian spectra, and a graph $G$ is said to be $L?DS$ (respectively, $Q?DS$) if there does not exist other non-isomorphic graph $H$ such that $H$ and $G$ are $L$-cospectral (respectively, $Q$-cospectral). Let $d_1\left(G\right)\ge d_2\left(G\right)\ge ?\ge d_n\left(G\right)$ be the degree sequence of a graph $G$ with $n$ vertices. In this paper, we prove that except for two exceptions (respectively, the graphs with $d_1\left(G\right)\in \{4,5\}$), if $H$ is $L$-cospectral (respectively, $Q$-cospectral) with a connected graph $G$ and $d_2\left(G\right)=2$, then $H$ has the same degree sequence as $G$. A spider graph is a unicyclic graph obtained by attaching some paths to a common vertex of the cycle. As an application of our result, we show that every spider graph and its complement graph are both $L?DS$, which extends the corresponding results of Haemers et al. (2008), Liu et al. (2011), Zhang et al. (2009) and Yu et al. (2014).     

Degree Ramsey numbers for even cycles

Let $H\stackrel{s}{?}G$ denote that any $s$-coloring of $E\left(H\right)$ contains a monochromatic $G$. The degree Ramsey number of a graph $G$, denoted by $R_{\Delta }(G,s)$, is $min\{\Delta \left(H\right):H\stackrel{s}{?}G\}$. We consider degree Ramsey numbers where $G$ is a fixed even cycle. Kinnersley, Milans, and West showed that $R_{\Delta }(C_{2k},s)\ge 2s$, and Kang and Perarnau showed that $R_{\Delta }(C_4,s)=\Theta \left(s^2\right)$. Our main result is that $R_{\Delta }(C_6,s)=\Theta \left(s^{3∕2}\right)$ and $R_{\Delta }(C_{10},s)=\Theta \left(s^{5∕4}\right)$. Additionally, we substantially improve the lower bound for $R_{\Delta }(C_{2k},s)$ for general $k$.     

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$.     

Strong vertex-magic and edge-magic labelings of 2-regular graphs of odd order using Kotzig completion

Let $G$ be a 2-regular graph with $2m+1$ vertices and assume that $G$ has a strong vertex-magic total labeling. It is shown that the four graphs $G\cup 2m{C}_3$, $G\cup (2m+2)C_3$, $G\cup m{C}_8$ and $G\cup (m+1)C_8$ also have a strong vertex-magic total labeling. These theorems follow from a new use of carefully prescribed Kotzig arrays. To illustrate the power of this technique, we show how just three of these arrays, combined with known labelings for smaller 2-regular graphs, immediately provide strong vertex-magic total labelings for 68 different 2-regular graphs of order 49.     

Counting arithmetical structures on paths and cycles

Let $G$ be a finite, connected graph. An arithmetical structure on $G$ is a pair of positive integer vectors $\mathbf{d},\mathbf{r}$ such that $(diag\left(\mathbf{d}\right)?A)\mathbf{r}=0$, where $A$ is the adjacency matrix of $G$. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices $(diag\left(\mathbf{d}\right)?A)$). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients $\left(\genfrac{}{}{0ex}{}{2n?1}{n?1}\right)$, and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.     

A degree sum condition for graphs to be covered by two cycles

Let $G$ be a $k$-connected graph of order $n$. In [1], Bondy (1980) considered a degree sum condition for a graph to have a Hamiltonian cycle, say, to be covered by one cycle. He proved that if ${\sigma }_{k+1}\left(G\right)>(k+1)(n?1)/2$, then $G$ has a Hamiltonian cycle. On the other hand, concerning a degree sum condition for a graph to be covered by two cycles, Enomoto et al. (1995) [4] proved that if $k=1$ and ${\sigma }_3\left(G\right)\ge n$, then $G$ can be covered by two cycles. By these results, we conjecture that if ${\sigma }_{2k+1}\left(G\right)>(2k+1)(n?1)/3$, then $G$ can be covered by two cycles. In this paper, we prove the case $k=2$ of this conjecture. In fact, we prove a stronger result; if $G$ is 2-connected with ${\sigma }_5\left(G\right)\ge 5(n?1)/3$, then $G$ can be covered by two cycles, or $G$ belongs to an exceptional class.     

The NLC-width and clique-width for powers of graphs of bounded tree-width

The $k$-power graph of a graph $G$ is a graph with the same vertex set as $G$, in that two vertices are adjacent if and only if, there is a path between them in $G$ of length at most $k$. A $k$-tree-power graph is the $k$-power graph of a tree, a $k$-leaf-power graph is the subgraph of some $k$-tree-power graph induced by the leaves of the tree.We show that (1) every $k$-tree-power graph has NLC-width at most $k+2$ and clique-width at most $k+2+max\{?\frac{k}{2}??1,0\}$, (2) every $k$-leaf-power graph has NLC-width at most $k$ and clique-width at most $k+max\{?\frac{k}{2}??2,0\}$, and (3) every $k$-power graph of a graph of tree-width $l$ has NLC-width at most ${(k+1)}^{l+1}?1$, and clique-width at most $2?{(k+1)}^{l+1}?2$.     

A sharp lower bound on Steiner Wiener index for trees with given diameter

Let $G$ be a connected graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. For a subset $S$ of $V\left(G\right)$, the Steiner distance$d\left(S\right)$ of $S$ is the minimum size of a connected subgraph whose vertex set contains $S$. For an integer $k$ with $2\le k\le n?1$, the Steiner$k$-Wiener index${\text{SW}}_k\left(G\right)$ is ${\sum }_{S?V\left(G\right),\left|S\right|=k}d\left(S\right)$. In this paper, we introduce some transformations for trees that do not increase their Steiner $k$-Wiener index for $2\le k\le n?1$. Using these transformations, we get a sharp lower bound on Steiner $k$-Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well.     

A note on Bartholdi zeta function and graph invariants based on resistance distance

Let $G$ be a finite connected graph. In this note, we show that the complexity of $G$ can be obtained from the partial derivatives at $(1?\frac{1}{t},t)$ of a determinant in terms of the Bartholdi zeta function of $G$. Moreover, the second order partial derivatives at $(1?\frac{1}{t},t)$ of this determinant can all be expressed as the linear combination of the Kirchhoff index, the additive degree-Kirchhoff index, and the multiplicative degree-Kirchhoff index of the graph $G$.     

Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph $G$ with $\Delta \left(G\right)?\delta \left(G\right)\le 1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for $k$-regular graphs with $4\le k\le 6$. All counterexamples for $k$-regular graphs $(k\ge 7)$ given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $k\le 4$.