摘要：
A spanning subgraph H of a graph G is a
$$P_{3}$$
-factor of G if every component of H is a path of order three. The square of a graph G, denoted by
$$G^{2}$$
, is the graph with vertex set V(G) such that two vertices are adjacent in
$$G^{2}$$
if and only if their distance in G is at most 2. A graph G is subcubic if it has maximum degree at most three. In this paper, we give a sharp necessary condition for the existence of
$$P_{3}$$
-factors in the square of a tree, which improves a result of Li and Zhang (Graphs Combin 24:107–111, 2008). In addition, we will also present a sufficient condition for the existence of
$$P_{3}$$
-factors in the square of a tree, which has the following interesting application to subcubic trees: if T is a subcubic tree of order 3n such that
$$|L(T-L(T))|\le 7$$
, then
$$T^{2}$$
has a
$$P_{3}$$
-factor, where L(T) denotes the set of leaves in T. Examples show that the upper bound 7 on
$$|L(T-L(T))|$$
is sharp.
期刊：
Applied Mathematics and Computation,2020年377:125149 ISSN：0096-3003
通讯作者：
Zou, Yan
作者机构：
[Zou, Yan; Hu, Zhiquan] Cent China Normal Univ, Fac Math & Stat, Wuhan, Peoples R China.
通讯机构：
[Zou, Yan] C;Cent China Normal Univ, Fac Math & Stat, Wuhan, Peoples R China.
关键词：
Edge prorating number;Path two bipancyclic;Bipanconnected;Bipartite graph
摘要：
Given a bipartite graph G = (A(1), A(2), E) with m := min {vertical bar A(1)vertical bar, |vertical bar A(2)vertical bar} >= 2, the edge prorating number for x is an element of A(i) is defined as rho(G)(x) = (d(x) - 1)/vertical bar A(3-i)vertical bar, i = 1, 2. Set.(G) := min {rho(G)(x): x is an element of A(1) boolean OR A(2)} and call it the minimum edge prorating number of G. We call G path two bipancyclic if for every path P of length two in G, and for every integer k is an element of [2, m], G has a 2k-cycle passing through P. In this article, it is shown that the minimum edge prorating number condition rho(G) >= 1/2 implies that a bipartite graph G is either path two bipancyclic or isomorphic to G(2n,4), where n >= 3 and G(2n,4) is a 2n by 4 bipartite graph. As an application, we proved that the minimum edge prorating number condition rho(G) = 1/2 also implies the bipanconnectivity of a bipartite graph G: for every pair u, v of distinct vertices, and for every appropriate integer l is an element of [2, 2m], G has a u, v-path of length l. This unifies the known results in Tian and Zang (1989) and Du et al. (2018). Examples show that the minimum edge prorating number condition rho(G) = 1/2 in both of our results are sharp. (C) 2020 Published by Elsevier Inc.
作者机构：
[Song, Fei-fei] Henan Agr Univ, Dept Informat & Computat Sci, Zhengzhou 450002, Peoples R China.;[Hu, Zhi-quan] Cent China Normal Univ, Fac Math & Stat, Wuhan 430079, Peoples R China.
作者机构：
[Min Liu] College of Economics, Northwest University of Political Science and Law, Xi’an, Shaanxi, China;[Zhiquan Hu] School of Mathematics and Statistics, Central China Normal University, Wuhan, Hubei, China
通讯机构：
[Min Liu] C;College of Economics, Northwest University of Political Science and Law, Xi’an, Shaanxi, China
摘要：
For a fixed graph $F$, a graph $G$ is $F$-saturated if it has no $F$ as a subgraph, but does contain $F$ after the addition of any new edge. The saturation number, sat$\left( {n,F} \right)$, is the minimum number of edges of a graph in the set of all $F$-saturated graphs with order $n$. In this paper, we determine the saturation number sat$\left( {n,2{P_3} \cup t{P_2}} \right)$ and characterize the extremal graphs for $n \ge 6t + 8$.
期刊：
Journal of Graph Theory,2018年87(3):374-393 ISSN：0364-9024
通讯作者：
Song, Feifei
作者机构：
[Song, Feifei; Hu, Zhiquan] Cent China Normal Univ, Fac Math & Stat, Wuhan, Hubei, Peoples R China.;[Song, Feifei] Henan Agr Univ, Dept Informat & Computat Sci, Zhengzhou, Henan, Peoples R China.
通讯机构：
[Song, Feifei] C;[Song, Feifei] H;Cent China Normal Univ, Fac Math & Stat, Wuhan, Hubei, Peoples R China.;Henan Agr Univ, Dept Informat & Computat Sci, Zhengzhou, Henan, Peoples R China.
摘要：
<jats:title>Abstract</jats:title><jats:p>In this article, we consider the following problem proposed by Locke and Zhang in 1991: Let <jats:italic>G</jats:italic> be a <jats:italic>k</jats:italic>‐connected graph with minimum degree <jats:italic>d</jats:italic> and <jats:italic>X</jats:italic> a set of <jats:italic>m</jats:italic> vertices on a cycle of <jats:italic>G</jats:italic>. For which values of <jats:italic>m</jats:italic> and <jats:italic>k</jats:italic>, with <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22164-math-0003.png" xlink:title="urn:x-wiley:03649024:media:jgt22164:jgt22164-math-0003" />, must <jats:italic>G</jats:italic> have a cycle of length at least <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22164-math-0004.png" xlink:title="urn:x-wiley:03649024:media:jgt22164:jgt22164-math-0004" /> passing through <jats:italic>X</jats:italic>? Fujisawa and Yamashita solved this problem for the case <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22164-math-0005.png" xlink:title="urn:x-wiley:03649024:media:jgt22164:jgt22164-math-0005" /> and <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22164-math-0006.png" xlink:title="urn:x-wiley:03649024:media:jgt22164:jgt22164-math-0006" /> in 2008. We provide an affirmative answer to this problem for the case of <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22164-math-0007.png" xlink:title="urn:x-wiley:03649024:media:jgt22164:jgt22164-math-0007" /> and <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22164-math-0008.png" xlink:title="urn:x-wiley:03649024:media:jgt22164:jgt22164-math-0008" />.</jats:p>
作者机构：
[Lin, Hou-yuan] Shandong Univ Finance & Econ, Sch Math & Quantitat Econ, Jinan 250014, Peoples R China.;[Hu, Zhi-quan] Cent China Normal Univ, Fac Math & Stat, Wuhan 430079, Peoples R China.
通讯机构：
[Lin, Hou-yuan] S;[Hu, Zhi-quan] C;Shandong Univ Finance & Econ, Sch Math & Quantitat Econ, Jinan 250014, Peoples R China.;Cent China Normal Univ, Fac Math & Stat, Wuhan 430079, Peoples R China.
作者机构：
[Jing Sun] School of Mathematics and Economics, Hubei University of Education, Wuhan 430205, Hubei, China;[Zhiquan Hu] School of Mathematics and Statistics, Central China Normal University, Wuhan 430079, Hubei, China
通讯机构：
[Jing Sun] S;School of Mathematics and Economics, Hubei University of Education, Wuhan 430205, Hubei, China
摘要：
Let G = (V_1,V_2,E) be a balanced bipartite graph with 2n vertices. The bipartite binding number of G, denoted by B(G), is defined to be n if G =K_n and min min | N(S) | / | S | otherwise. We call G bipancyclic if it contains a cycle of every even length m for 4≤m≤2n. A theorem showed that if G is a balanced bipartite graph with 2n vertices, B(G)>3 / 2 and n≥139, then G is bipancyclic. This paper generalizes the conclusion as follows: Let 0<c<3 / 2 and G be a 2-connected balanced bipartite graph with 2n (n is large enough) vertices such that B(G)≥c and δ (G)≥(2 - c)n / (3 - c) + 2 / 3. Then G is bipancyclic.
摘要：
A graph G is
$$\{X,Y\}$$
-free if it contains neither X nor Y as an induced subgraph. Pairs of connected graphs X,Y such that every 3-connected
$$\{X,Y\}$$
-free graph is Hamilton-connected have been investigated recently in (2002, 2000, 2012). In this paper, it is shown that every 3-connected
$$\{K_{1,3},N_{1,2,3}\}$$
-free graph is Hamilton-connected, where
$$N_{1,2,3}$$
is the graph obtained by identifying end vertices of three disjoint paths of lengths 1,2,3 to the vertices of a triangle.
作者机构：
[Hu, Zhiquan] Cent China Normal Univ, Fac Math & Stat, Wuhan, Peoples R China.;[Sun, Jing] Hubei Univ Educ, Fac Math & Stat, Wuhan, Peoples R China.
通讯机构：
[Hu, Zhiquan] C;Cent China Normal Univ, Fac Math & Stat, Wuhan, Peoples R China.
摘要：
We investigate the set of cycle lengths occurring in bipartite graphs with large minimum degree. A bipartite graph is weakly bipancyclic if it contains cycles of every even length between the length of a shortest and a longest cycle. In this paper, it is shown that if G = (V-1, V-2, E) is a bipartite graph with minimum degree at least n/3 + 4, where n = max {[V-1], [V-2]}, then G is a weakly bipancyclic graph of girth 4. This improves a theorem of Tian and Zang (1989), which asserts that if G is a Hamilton bipartite graph on 2n(n >= 60) vertices with minimum degree greater than 2n/5 + 2, then G is bipancyclic (i.e., G contains cycles of every even length between 4 and 2n). By combining the main result of our paper with a theorem of Jackson and Li (1994), we obtain that every 2-connected k-regular bipartite graph on at most 6k - 38 vertices is bipancyclic. (C) 2015 Elsevier B.V. All rights reserved.
作者机构：
[Chen Yuan; Hu ZhiQuan] Cent China Normal Univ, Fac Math & Stat, Wuhan 430079, Peoples R China.;[Chen Yuan] Wuhan Text Univ, Coll Math & Comp Sci, Wuhan 430073, Peoples R China.;[Chen GuanTao] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA.
通讯机构：
[Chen Yuan] C;Cent China Normal Univ, Fac Math & Stat, Wuhan 430079, Peoples R China.
摘要：
A tree with atmost m leaves is called an m-ended tree. Kyaw proved that every connected K
1,4-free graph with σ
4(G) ⩽ n−1 contains a spanning 3-ended tree. In this paper we obtain a result for k-connected K
1,4-free graphs with k ⩽ 2. Let G be a k-connected K
1,4-free graph of order n with k ⩽ 2. If σ
k+3(G) ⩽ n+2k −2, then G contains a spanning 3-ended tree.
期刊：
Journal of Graph Theory,2014年77(3):237-250 ISSN：0364-9024
通讯作者：
Chen, Guantao
作者机构：
[Chen, Guantao] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA.;[Ferrara, Michael; Jacobson, Michael] Univ Colorado Denver, Dept Math & Stat Sci, Denver, CO USA.;[Hu, Zhiquan] Cent China Normal Univ, Fac Math & Stat, Wuhan, Peoples R China.;[Liu, Huiqing] Hubei Univ, Sch Math & Comp Sci, Wuhan, Peoples R China.
通讯机构：
[Chen, Guantao] G;Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA.
关键词：
extremal spanning tree;broom
摘要：
A broom is a tree obtained by subdividing one edge of the star an arbitrary number of times. In (E. Flandrin, T. Kaiser, R. Kužel, H. Li and Z. Ryjáček, Neighborhood Unions and Extremal Spanning Trees, Discrete Math 308 (2008), 2343–2350) Flandrin et al. posed the problem of determining degree conditions that ensure a connected graph G contains a spanning tree that is a broom. In this article, we give one solution to this problem by demonstrating that if G is a connected graph of order with , then G contains a spanning broom. This result is best possible.
期刊：
Graphs and Combinatorics,2013年29(6):1755-1775 ISSN：0911-0119
通讯作者：
Lin, Houyuan
作者机构：
[Lin, Houyuan; Hu, Zhiquan] Cent China Normal Univ, Fac Math & Stat, Wuhan 430079, Peoples R China.;[Lin, Houyuan] Shandong Univ Finance & Econ, Sch Math & Quantitat Econ, Jinan 250014, Peoples R China.
通讯机构：
[Lin, Houyuan] S;Shandong Univ Finance & Econ, Sch Math & Quantitat Econ, Jinan 250014, Peoples R China.
摘要：
For integers i , j , k with $${i\geq j\geq k\geq 0}$$ , let N i , j , k be the graph obtained by identifying end vertices of three disjoint paths of lengths i , j , k to the vertices of a triangle. In this paper, we show that every 3-connected { K 1,3, N i , 7- i , 2}-free graph is hamiltonian, where $${i \in \{4,5\}}$$ . This result is sharp in the sense that no one of the numbers i , 7 i and 2 in N i , 7- i , 2 can be replaced by a larger number. For integers i , j , k with $${i\geq j\geq k\geq 0}$$ , let N i , j , k be the graph obtained by identifying end vertices of three disjoint paths of lengths i , j , k to the vertices of a triangle. In this paper, we show that every 3-connected { K 1,3, N i , 7- i , 2}-free graph is hamiltonian, where $${i \in \{4,5\}}$$ . This result is sharp in the sense that no one of the numbers i , 7 i and 2 in N i , 7- i , 2 can be replaced by a larger number.
期刊：
SIAM JOURNAL ON DISCRETE MATHEMATICS,2013年27(2):597-618 ISSN：0895-4801
通讯作者：
Law, Ka Ho
作者机构：
[Hu, Zhiquan] Cent China Normal Univ, Fac Math & Stat, Wuhan, Peoples R China.;[Law, Ka Ho; Zang, Wenan] Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China.
通讯机构：
[Law, Ka Ho] U;Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China.
摘要：
Let G = (V-1, V-2, E) be a balanced bipartite graph with 2n vertices. The bipartite binding number of G, denoted by B(G), is defined to be n if G = K-n,K-n and min(i is an element of {1,2}) min (empty set not equal S subset of Vi vertical bar N(S)vertical bar < n) vertical bar N(S)vertical bar/vertical bar S vertical bar otherwise. We call G bipancyclic if it contains a cycle of every even length m for 4 <= m <= 2n. The purpose of this paper is to show that if B(G) > 3/2 and n >= 139, then G is bipancyclic; the bound 3/2 is best possible in the sense that there exist infinitely many balanced bipartite graphs G that have B(G) = 3/2 but are not Hamiltonian.
作者机构：
[Lin HouYuan] Shandong Univ Finance & Econ, Sch Math & Quantitat Econ, Jinan 250014, Peoples R China.;[Hu ZhiQuan; Lin HouYuan] Cent China Normal Univ, Fac Math & Stat, Wuhan 430079, Peoples R China.
通讯机构：
[Lin HouYuan] S;Shandong Univ Finance & Econ, Sch Math & Quantitat Econ, Jinan 250014, Peoples R China.
摘要：
For non-negative integers i, j and k, let N
i,j,k
be the graph obtained by identifying end vertices of three disjoint paths of lengths i, j and k to the vertices of a triangle. In this paper, we prove that every 3-connected {K
1,3,N
3,3,3}-free graph is Hamiltonian. This result is sharp in the sense that for any integer i > 3, there exist infinitely many 3-connected {K
1,3,N
i,3,3}-free non-Hamiltonian graphs.
期刊：
Bulletin of the Malaysian Mathematical Sciences Society,2012年35(4):969-974 ISSN：0126-6705
通讯作者：
Ye, Chengfu
作者机构：
[Ye, Chengfu] Qinghai Normal Univ, Dept Math, Xining 810008, Qinghai, Peoples R China.;[Ye, Chengfu; Hu, Zhiquan] Huazhong Normal Univ, Coll Math & Stat, Wuhan, Hubei, Peoples R China.
通讯机构：
[Ye, Chengfu] Q;Qinghai Normal Univ, Dept Math, Xining 810008, Qinghai, Peoples R China.
关键词：
Tree;pendent vertices;index
摘要：
The Merrifield-Simmons index of a graph is defined as the total number of the independent sets of the graph and the Hosoya index of a graph is defined as the total number of the matchings of the graph. In this paper, among all the trees with n vertices and k pendent vertices, we determine the trees with the first [n - k + 1/2] largest Merrifield-Simmons index and the trees with the first [n - k +1/2] sma llest Hosoya index
作者机构：
[Chen, Guantao] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA.;[Hu, Zhiquan] Cent China Normal Univ, Fac Math & Stat, Wuhan 430079, Peoples R China.;[Li, Hao] Univ Paris Sud, LRI, UMR CNRS UPS 8623, F-91405 Orsay, France.
通讯机构：
[Chen, Guantao] G;Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA.
会议名称：
8th French Combinatorial Conference (FCC)
会议时间：
JUN 28-JUL 02, 2010
会议地点：
Orsay, FRANCE
会议主办单位：
[Chen, Guantao] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA.^[Hu, Zhiquan] Cent China Normal Univ, Fac Math & Stat, Wuhan 430079, Peoples R China.^[Li, Hao] Univ Paris Sud, LRI, UMR CNRS UPS 8623, F-91405 Orsay, France.
关键词：
Cycle;Path;Degree;Toughness;Connectivity
摘要：
A path in a graph is called extendable if it is a proper subpath of another path. A graph is locally connected if every neighborhood induces a connected subgraph. We show that, for each graph G of order n, there exists a threshold number s such that every path of order smaller than s is extendable and there exists a non-extendable path of order t for each t is an element of {s, ... , n - 1} if G satisfies any one of the following three conditions: the degree sum d(u) + d(nu) >= n for any two nonadjacent vertices u and nu; P-4-free and omega(G - S) <= vertical bar S vertical bar for every cut set S of G: connected, locally connected, and K-1.3-free where P-4 and K-1,K-3 denote a path of order 4 and a complete bipartite graph with 1 and 3 vertices in each color class, respectively. (C) 2011 Elsevier B.V. All rights reserved.
