Search

A graph is called equimatchable if all of its maximal matchings have the same size. Due to Eiben and Kotrbcik, any connected graph with odd order and independence number $\alpha(G)$ at most $2$ is equimatchable. Akbari et al. showed that for any odd number $r$, a connected equimatchable $r$-regular graph must be either the complete graph $K_{r+1}$ or the complete bipartite graph $K_{r,r}$. They also determined all connected equimatchable $4$-regular graphs and proved that for any even $r$, any connected equimatchable $r$-regular graph is either $K_{r,r}$ or factor-critical. In this paper, we confirm that for any even $r\ge 6$, there exists a unique connected equimatchable $r$-regular graph $G$ with $\alpha(G)\geq 3$ and odd order., Comment: 22 Pages and 5 figures

Tutte proved that 4-connected planar graphs are Hamiltonian. It is unknown if there is an analogous result on 1-planar graphs. In this paper, we characterize 4-connected 1-planar chordal graphs, and show that all such graphs are Hamiltonian-connected. A crucial tool used in our proof is a characteristic of 1-planar 4-trees.

A graph $G$ is said to be crossing-critical if $cr(G-e)< cr(G)$ for every edge $e$ of $G$, where $cr(G)$ is the crossing number of $G$. Richter and Thomassen [Journal of Combinatorial Theory, Series B 58 (1993), 217-224] constructed an infinite family of 4-regular crossing-critical graphs with crossing number $3$. In this article, we present a new infinite family of 4-regular crossing-critical graphs.

Recently, Chmutov proved that the partial-dual polynomial considered as a function on chord diagrams satisfies the four-term relations. In this paper, we show that this function on framed chord diagrams also satisfies the four-term relations, i.e., is a framed weight system., Comment: 10pages, 11figures

A {\it mixed hypergraph} ${\cal H}=({\cal V},{\cal C},{\cal D})$ consists of the vertex set ${\cal V}$ and two families of subsets of $2^{{\cal V}}$: the family ${\cal C}$ of co-edges and the family ${\cal D}$ of edges. ${\cal H}$ is said to be colorable if there is a mapping $f$ from ${\cal V}$ to the set of positive integers such that $|\{f(v):v\in e\}|<|e|$ for each $e\in {\cal C}$ and $|\{f(v):v\in e\}|>1$ for each $e\in {\cal D}$. There exist mixed hypergraphs which are uncolorable, and quite little about these mixed hypergraphs is known. A mixed hypergraph is called a bi-hypergraph if its co-edge set and edge set are the same. In this article, we first apply Lov\'asz local lemma to show that any $r$-uniform bi-hypergraph with $r\ge 4$ is colorable if every edge is incident to less than $(r-1)^{r-1}e^{-1}-1$ other edges, where $e$ is the base of natural logarithms. Then, we show that among all the uncolorable $3$-uniform bi-hypergraphs, the smallest size of a minimal one is ten, which answers a question raised by Tuza and Voloshin in 2000. As an extension, we provide a minimal uncolorable $3$-uniform bi-hypergraph of order $n$ and size at most $\frac{7n}3-4$ for every $n\ge 6$., Comment: 19 pages, 4 figures

For a k-tree T, a generalization of a tree, the local mean order of sub-k-trees of T is the average order of sub-k-trees of T containing a given k-clique. The problem whether the largest local mean order of a tree (i.e., a 1-tree) at a vertex always takes on at a leaf was asked by Jamison in 1984 and was answered by Wagner and Wang in 2016. In 2018, Stephens and Oellermann asked a similar problem: for any k-tree T, does the maximum local mean order of sub-k-trees containing a given k-clique occur at a k-clique that is not a major k-clique of T? In this paper, we give it an affirmative answer.

In 2013, Ku and Wong showed that for any partitions $\mu$ and $\mu'$ of a positive integer $n$ with the same first part $u$ and the lexicographic order $\mu\triangleleft \mu'$, the eigenvalues $\xi_{\mu}$ and $\xi_{\mu'}$ of the derangement graph $\Gamma_n$ have the property $|\xi_{\mu}|\le |\xi_{\mu'}|$, where the equality holds if and only if $u=3$ and all other parts are less than $3$. In this article, we obtain an analogous conclusion on the eigenvalues of the perfect matching derangement graph $\mathcal{M}_{2n}$ of $K_{2n}$ by finding a new recurrence formula for the eigenvalues of $\mathcal{M}_{2n}$., Comment: 13 pages

Let ${\cal H}=(V,E)$ be any $r$-uniform hypergraph with $n$ vertices and $m$ edges, where $r\ge 2$, $P({\cal H},k)$ be the chromatic polynomial of ${\cal H}$, $P({\cal H},L)$ be the number of $L$-colorings of ${\cal H}$ for any $k$-assignment $L$ and $P_l({\cal H},k)$ be the minimum value of $P({\cal H},L)$ over all $k$-assignments $L$. In this article, we show that $P_l({\cal H},k)=P({\cal H},k)$ holds whenever $k\ge m-1$, and in particular, $P({\cal H}, L)-P({\cal H},k)\ge (k-m+1)k^{n-r-1} \sum\limits_{e\in E} \left (k-\left|\bigcap\limits_{v\in e}L(v)\right|\right ) $ when $m\ge 5$. Our conclusion extends both our previous result in terms of graphs and the latest known result on hypergraphs by Wang, Qian and Yan., Comment: 1 figure and 14 pages

For any $r$-uniform hypergraph $\mathcal{H}$ with $m$ ($\geq 2$) edges, let $P(\mathcal{H},k)$ and $P_l(\mathcal{H},k)$ be the chromatic polynomial and the list-color function of $\mathcal{H}$ respectively, and let $\rho(\mathcal{H})$ denote the minimum value of $|e\setminus e'|$ among all pairs of distinct edges $e,e'$ in $\mathcal{H}$. We will show that if $r\ge3$, $\rho(\mathcal{H})\ge 2$ and $m\ge \frac{\rho(\mathcal{H})^3}2+1$, then $P_l(\mathcal{H},k)=P(\mathcal{H},k)$ holds for all integers $k\geq \frac{2.4(m-1)}{\rho(\mathcal{H})\log(m-1)}$., Comment: 11 pages, 1 figure

For a hypergraph ${\cal H}$, let $P({\cal H},k)$ and $P_l({\cal H},k)$ be its chromatic polynomial and list-color function respectively, and let $\tau'({\cal H})$ be the least non-negative integer $q$ such that $P({\cal H},k)=P_l({\cal H},k)$ holds for all integers $k\ge q$. In this article, we show that for any $r$-uniform hypergraph ${\cal H}$ of order $n$ and size $m$ and any $k$-assignment $L$ of ${\cal H}$, where $r\ge 3$, $P({\cal H},L)-P({\cal H},k)\ge \min \{0.02k, k-(m-1)\} k^{n-r-1}\sum_{e\in E({\cal H})} \left ( k-\left |\bigcap_{v\in e}L(v)\right | \right )$ holds for $k\ge m-1\ge 4$. It follows that $\tau'({\cal H})\le m-1$, improving the current best result on $\tau'({\cal H})$., Comment: This article is a sister paper of "Compare list-color functions of uniform hypergraphs with their chromatic polynomials (I)" at arXiv:2305.02497. The later is now completed in a new approach, and it covers the main result in the former

A matching of a graph is a set of edges without common end vertex. A graph is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. Recently, Biedl and Wittnebel proved that every 1-planar graph with minimum degree 3 and $n\geq 7$ vertices has a matching of size at least $\frac{n+12}{7}$, which is tight for some graphs. They also provided tight lower bounds for the sizes of matchings in 1-planar graphs with minimum degree 4 or 5. In this paper, we show that any 1-planar graph with minimum degree 6 and $n \geq 36$ vertices has a matching of size at least $\frac{3n+4}{7}$, and this lower bound is tight. Our result confirms a conjecture posed by Biedl and Wittnebel., Comment: 19 pages and 5 figures. To appear in SIAM Discrete Mathematics

Let $G=(V,E)$ be a simple graph with $n$ vertices and $m$ edges, $P(G,k)$ be the chromatic polynomial of $G$, and $P(G,L)$ be the number of $L$-colorings of $G$ for any $k$-assignment $L$. In this article, we show that when $k\ge m-1\ge 3$, $P(G,L)-P(G,k)$ is bounded below by $\left ( (k-m+1)k^{n-3}+\frac{(k-m+3)c}{3} k^{n-5}\right )\sum\limits_{uv\in E}|L(u)\setminus L(v)|$, where $c\ge \frac{(m-1)(m-3)}{8}$, and in particular, if $G$ is $K_3$-free, then $c\ge {m-2\choose 2}+2\sqrt m-3$. Consequently, $P(G,L)\ge P(G,k)$ whenever $k\ge m-1$., Comment: 12 pages

For any connected graph $G$, let $P(G,m)$ and $P_{DP}(G,m)$ denote the chromatic polynomial and DP color function of $G$, respectively. It is known that $P_{DP}(G,m)\le P(G,m)$ holds for every positive integer $m$. Let $DP_\approx$ (resp. $DP_<$) be the set of graphs $G$ for which there exists an integer $M$ such that $P_{DP}(G,m)=P(G,m)$ (resp. $P_{DP}(G,m)

Let $G$ be a complete multi-partite graph of order $n$. In this paper, we consider the anti-Ramsey number $ar(G,\mathcal{T}_{q})$ with respect to $G$ and the set $\mathcal{T}_{q}$ of trees with $q$ edges, where $2\le q\le n-1$. For the case $q=n-1$, the result has been obtained by Lu, Meier and Wang. We will extend it to $q

DP-coloring was introduced by Dvo\v{r}\'{a}k and Postle and is a generalization of proper coloring. For any graph $G$, let $\chi(G)$ and $\chi_{DP}(G)$ denote the chromatic number and the DP-chromatic number of $G$ respectively. In this article, we show that $\chi_{DP}(G \vee K_s)=\chi(G \vee K_s)$ holds for $s=\left \lceil \frac{4(k+1)m}{2k+1} \right \rceil \le \lceil 2.4m\rceil$, where $k=\chi(G)$, $m=|E(G)|$ and $G \vee K_s$ is the join of $G$ and the complete graph $K_s$. Hence $Z_{DP}(n)\le n^2-(n+3)/2$ holds for every integer $n \ge 2$, where $Z_{DP}(n)$ is the minimum natural number $s$ such that $\chi_{DP}(G \vee K_s)=\chi(G \vee K_s)$ holds for every graph $G$ of order $n$. Our result improves the best current upper bound $Z_{DP}(n)\le 1.5n^2$ due to Bernshteyn, Kostochka and Zhu., Comment: 18 pages, 5 figures

It is well-known that the number of spanning trees, denoted by $\tau(G)$, in a connected multi-graph $G$ can be calculated by the Matrix-Tree theorem and Tutte's deletion-contraction theorem. In this short note, we find an alternate method to compute $\tau(G)$ by degrees of vertices., Comment: 9 pages, 2 figures

For any graph $G$, the chromatic polynomial of $G$ is the function $P(G,m)$ which counts the number of proper $m$-colorings of $G$ for each positive integer $m$. The DP color function $P_{DP}(G,m)$ of $G$, introduced by Kaul and Mudrock in 2019, is a generalization of $P(G,m)$ with $P_{DP}(G,m)\le P(G,m)$ for each positive integer $m$. Let $P_{DP}(G)\approx P(G)$ (resp. $P_{DP}(G)< P(G)$) denote the property that $P_{DP}(G,m)=P(G,m)$ (resp. $P_{DP}(G,m)

In this article, we extend Moon's classic formula for counting spanning trees in complete graphs containing a fixed spanning forest to complete bipartite graphs. Let $(X,Y)$ be the bipartition of the complete bipartite graph $K_{m,n}$ with $|X|=m$ and $|Y|=n$. We prove that for any given spanning forest $F$ of $K_{m,n}$ with components $T_1,T_2,\ldots,T_k$, the number of spanning trees in $K_{m,n}$ which contain all edges in $F$ is equal to $$ \frac 1{mn}\left(\prod_{i=1}^k (m_in+n_im)\right) \left (1-\sum_{i=1}^{k}\frac{m_in_i}{m_in+n_im}\right ), $$ where $m_i=|V(T_i)\cap X|$ and $n_i=|V(T_i)\cap Y|$ for $i=1,2,\ldots,k$.

A graph is called $1$-planar if it admits a drawing in the plane such that each edge is crossed at most once. Let $G$ be a bipartite 1-planar graph with $n$ ($\ge 4$) vertices and $m$ edges. Karpov showed that $m\le 3n-8$ holds for even $n\ge 8$ and $m\le 3n-9$ holds for odd $n\ge 7$. Czap, Przybylo and \u{S}krabul\'{a}kov\'{a} proved that if the partite sets of $G$ are of sizes $x$ and $y$, then $m\le 2n+6x-12$ holds for $2\leq x\leq y$, and conjectured that $m\le 2n+4x-12$ holds for $x\ge 3$ and $y\ge 6x-12$. In this paper, we settle their conjecture and our result is even under a weaker condition $2\le x\le y$., Comment: 20 pages, 6 figures

For a simple graph $G$, let $\chi(G,x)$ denote the chromatic polynomial of $G$. This manuscript introduces some polynomials which are related to chromatic polynomial and their relations., Comment: 74 pages, more than 10 figures and 62 references

For a bridgeless graph $G$, its flow polynomial is defined to be the function $F(G,q)$ which counts the number of nonwhere-zero $\Gamma$-flows on an orientation of $G$ whenever $q$ is a positive integer and $\Gamma$ is an additive Abelian group of order $q$. It was introduced by Tutte in 1950 and the locations of zeros of this polynomial have been studied by many researchers. This article gives a survey on the results and problems on the study of real zeros of flow polynomials., Comment: 19 pages, 4 figures and 50 references

A graph $G$ is {$k$-crossing-critical} if $cr(G)\ge k$, but $cr(G\setminus e)

A {\it tiered graph} $G=(V,E)$ with $m $ tiers is a simple graph with $V\subseteq \brk{n}$, where $\brk{n}=\{1,2,\cdots,n\}$, and with a surjective map $t$ from $V$ to $\brk{m}$ such that if $v$ is a vertex adjacent to $v'$ in $G$ with $v>v'$, then $t(v) >t(v')$. For any ordered partition $p=(p_1,p_2,\cdots,p_m)$ of $n$, let $\sett_p$ denote the set of tiered trees with vertex set $\brk{n}$ and with a map $t: \brk{n}\rightarrow \brk{m}$ such that $|t^{-1}(i)|=p_i$ for all $i=1,2,\ldots,m$. For any $T\in \sett_p$, let $K_T$ denote the complete tiered graph whose vertex set and tiering map are the same as those of $T$. If the edges of $K_T$ are ordered lexicographically by their endpoints, then the weight $w(T)$ of $T$ is the external activity of $T$ in $K_T$, i.e., the number of edges $e\in E(K_{T})\setminus E(T)$ such that $e$ is the least element in the unique cycle determined by $T\cup e$. Let $P_p(q)=\sum_{T\in \sett_{p}}q^{w(T)}$. Dugan, Glennon, Gunnells and Steingr\'imsson [J. Combin. Theory, Ser. A 164 (2019) pp. 24-49] asked for an elementary proof of the identity $P_p(q)=P_{\pi(p)}(q)$ for any permutation $\pi$ of $1,2,\cdots,m$, where $\pi(p)=p_{\pi(1)},p_{\pi(2)},\cdots,p_{\pi(m)})$. In this article, we will prove an extension of this identity by applying Tutte polynomials. Furthermore, we also provide a proof of the identity $P_{(1,p_1,p_2)}(q)=P_{(p_1+1,p_2+1)}(q)$ via Tutte polynomials.

A signed edge domination function (or SEDF) of a simple graph $G=(V,E)$ is a function $f: E\rightarrow \{1,-1\}$ such that $\sum_{e'\in N[e]}f(e')\ge 1$ holds for each edge $e\in E$, where $N[e]$ is the set of edges in $G$ that share at least one endpoint with $e$. Let $\gamma_s'(G)$ denote the minimum value of $f(G)$ among all SEDFs $f$, where $f(G)=\sum_{e\in E}f(e)$.In 2005, Xu conjectured that $\gamma_s'(G)\le n-1$, where $n$ is the order of $G$. This conjecture has been proved for the two cases $v_{odd}(G)=0$ and $v_{even}(G)=0$, where $v_{odd}(G)$ (resp. $v_{even}(G)$) is the number of odd (resp. even) vertices in $G$. This article proves Xu's conjecture for $v_{even}(G)\in \{1, 2\}$. We also show that for any simple graph $G$ of order $n$, $\gamma_s'(G)\le n+v_{odd}(G)/2$ and $\gamma_s'(G)\le n-2+v_{even}(G)$ when $v_{even}(G)>0$, and thus $\gamma_s'(G)\le (4n-2)/3$. Our result improves the best current upper bound of $\gamma_s'(G)\le \lceil 3n/2\rceil$.

A complex unit gain graph (or ${\mathbb T}$-gain graph) is a triple $\Phi=(G, {\mathbb T}, \varphi)$ (or $(G, \varphi)$ for short) consisting of a simple graph $G$, as the underlying graph of $(G, \varphi)$, the set of unit complex numbers $\mathbb{T}= \{ z \in C:|z|=1 \}$ and a gain function $\varphi: \overrightarrow{E} \rightarrow \mathbb{T}$ with the property that $\varphi(e_{i,j})=\varphi(e_{j,i})^{-1}$. In this paper, we prove that $2m(G)-2c(G) \leq r(G, \varphi) \leq 2m(G)+c(G)$, where $r(G, \varphi)$, $m(G)$ and $c(G)$ are the rank of the Hermitian adjacency matrix $H(G, \varphi)$, the matching number and the cyclomatic number of $G$, respectively. Furthermore, the complex unit gain graphs $(G, \mathbb{T}, \varphi)$ with $r(G, \varphi)=2m(G)-2c(G)$ and $r(G, \varphi)=2m(G)+c(G)$ are characterized. These results generalize the corresponding known results about undirected graphs, mixed graphs and signed graphs. Moreover, we show that $2m(G-V_{0}) \leq r(G, \varphi) \leq 2m(G)+b(G)$ holds for any subset $V_0$ of $V(G)$ such that $G-V_0$ is acyclic and $b(G)$ is the minimum integer $|S|$ such that $G-S$ is bipartite for $S \subset V(G)$.

Let $G=(V,E)$ be a simple graph with $V=\{1,2,\cdots,n\}$ and $\chi(G,x)$ be its chromatic polynomial. For an ordering $\pi=(v_1,v_2,\cdots,v_n)$ of elements of $V$, let $\delta_G(\pi)$ be the number of $i$'s, where $1\le i\le n-1$, with either $v_i

For any connected multigraph $G=(V,E)$ and any $M\subseteq E$, if $M$ induces an acyclic subgraph of $G$ and removing all edges in $M$ yields a subgraph of $G$ whose components are complete graphs, a formula for $\tau_G(M)$ is obtained, where $\tau_G(M)$ is the number of spanning trees in $G$ which contain all edges in $M$. Applying this result, we can easily obtain a formula for the number of spanning trees in the line graph or the middle graph of an arbitrary graph. Applying this result, we also show that for any connected graph $G$ with a clique $U$ which is a cut-set of $G$, the number of spanning trees in $G$ has a factorization which is analogous to a property of the chromatic polynomial of $G$., Comment: 26 pages, 9 figures and 18 references. Main results have been presented in Fuzhou University, Minan Normal University and Northwestern Polytechnical University

Using the theory of electrical network, we first obtain a simple formula for the number of spanning trees of a complete bipartite graph containing a certain matching or a certain tree. Then we apply the effective resistance (i.e., resistance distance in graphs) to find a formula for the number of spanning trees in the nearly complete bipartite graph $G(m,n,p)=K_{m,n}-pK_2$ $(p\leq \min\{m,n\})$, which extends a recent result by Ye and Yan who obtained the effective resistances and the number of spanning trees in $G(n,n,p)$. As a corollary, we obtain the Kirchhoff index of $G(m,n,p)$ which extends a previous result by Shi and Chen.

Let $G=(V,E)$ be a matching-covered graph and $X$ be an edge set of $G$. $X$ is said to be feasible if there exist two perfect matchings $M_1$ and $M_2$ in $G$ such that $|M_1\cap X|\not \equiv|M_2\cap X|\ (\mbox{mod } 2)$. For any $V_0\subseteq V$, $X$ is said to be switching-equivalent to $X\oplus \nabla_G(V_0)$, where $\nabla_G(V_0)$ is the set of edges in $G$ each of which has exactly one end in $V_0$ and $A \oplus B$ is the symmetric difference of two sets $A$ and $B$. Lukot'ka and Rollov\'a showed that when $G$ is regular and bipartite, $X$ is non-feasible if and only if $X$ is switching-equivalent to $\emptyset$. This article extends Lukot'ka and Rollov\'a's result by showing that this conclusion holds as long as $G$ is matching-covered and bipartite. This article also studies matching-covered graphs $G$ whose non-feasible edge sets are switching-equivalent to $\emptyset$ or $E$ and partially characterizes these matching-covered graphs in terms of their ear decompositions. Another aim of this article is to construct infinite many $r$-connected and $r$-regular graphs of class 1 containing non-feasible edge sets not switching-equivalent to either $\emptyset$ or $E$ for an arbitrary integer $r$ with $r\ge 3$, which provides negative answers to problems asked by Lukot'ka and Rollov\'a and He, et al respectively., Comment: 21 pages, 5 figures

In this paper, we prove that $(-\infty, 0)$ is a zero-free interval for chromatic polynomials of a family ${\cal L}_0$ of hypergraphs and $(0, 1)$ is a zero-free interval for chromatic polynomials of a subfamily ${\cal L}_0'$ of ${\cal L}_0$ of hypergraphs. These results extend known results on zero-free intervals of chromatic polynomials of graphs and hypergraphs., Comment: 4 figures, 16 references. Accepted by Discrete Mathematics

Let $G$ be a bridgeless graph. In 2011 Kung and Royle showed that all roots of the flow polynomial $F(G,\lambda)$ of $G$ are integers if and only if $G$ is the dual of a chordal and plane graph. In this article, we study whether a bridgeless graph $G$ for which $F(G,\lambda)$ has real roots only must be the dual of some chordal and plane graph. We conclude that the answer of this problem for $G$ is positive if and only if $F(G,\lambda)$ does not have any real root in the interval $(1,2)$. We also prove that for any non-separable and $3$-edge connected $G$, if $G-e$ is also non-separable for each edge $e$ in $G$ and every $3$-edge-cut of $G$ consists of edges incident with some vertex of $G$, then all roots of $P(G,\lambda)$ are real if and only if either $G\in \{L,Z_3,K_4\}$ or $F(G,\lambda)$ contains at least $9$ real roots in the interval $(1,2)$, where $L$ is the graph with one vertex and one loop and $Z_3$ is the graph with two vertices and three parallel edges joining these two vertices., Comment: 15 pages, 2 figures. To appear in EJC

The chromatic polynomial $P(G,x)$ of a graph $G$ of order $n$ can be expressed as $\sum\limits_{i=1}^n(-1)^{n-i}a_{i}x^i$, where $a_i$ is interpreted as the number of broken-cycle free spanning subgraphs of $G$ with exactly $i$ components. The parameter $\epsilon(G)=\sum\limits_{i=1}^n (n-i)a_i/\sum\limits_{i=1}^n a_i$ is the mean size of a broken-cycle-free spanning subgraph of $G$. In this article, we confirm and strengthen a conjecture proposed by Lundow and Markstr\"{o}m in 2006 that $\epsilon(T_n)< \epsilon(G)<\epsilon(K_n)$ holds for any connected graph $G$ of order $n$ which is neither the complete graph $K_n$ nor a tree $T_n$ of order $n$. The most crucial step of our proof is to obtain the interpretation of all $a_i$'s by the number of acyclic orientations of $G$., Comment: 20 pages, 23 references. To appear in J. Graph Theory

In this paper, we present some properties on chromatic polynomials of hypergraphs which do not hold for chromatic polynomials of graphs. We first show that chromatic polynomials of hypergraphs have all integers as their zeros and contain dense real zeros in the set of real numbers. We then prove that for any multigraph $G=(V,E)$, the number of totally cyclic orientations of $G$ is equal to the value of $|P(H,-1)|$, where $P(H,\lambda)$ is the chromatic polynomial of a hypergraph $H$ which is constructed from $G$. Finally we show that the multiplicity of root "$0$" of $P(H,\lambda)$ may be at least $2$ for some connected hypergraphs $H$, and the multiplicity of root "$1$" of $P(H,\lambda)$ may be $1$ for some connected and separable hypergraphs $H$ and may be $2$ for some connected and non-separable hypergraphs $H$., Comment: 3 figures, 22 pages, 48 references. Accepted for publication in the European Journal of Combinatorics

For any graph $G$, let $t(G)$ be the number of spanning trees of $G$, $L(G)$ be the line graph of $G$ and for any non-negative integer $r$, $S_r(G)$ be the graph obtained from $G$ by replacing each edge $e$ by a path of length $r+1$ connecting the two ends of $e$. In this paper we obtain an expression for $t(L(S_r(G)))$ in terms of spanning trees of $G$ by a combinatorial approach. This result generalizes some known results on the relation between $t(L(S_r(G)))$ and $t(G)$ and gives an explicit expression $t(L(S_r(G)))=k^{m+s-n-1}(rk+2)^{m-n+1}t(G)$ if $G$ is of order $n+s$ and size $m+s$ in which $s$ vertices are of degree $1$ and the others are of degree $k$. Thus we prove a conjecture on $t(L(S_1(G)))$ for such a graph $G$., Comment: 22 pages, 7 pages, presented at the National Conference of Combinatorics and Graph Theory at Guangzhou, China in Nov. 2014. It was submitted to JGT in Feb. 2014 and revised in July 2015