Light subgraphs in graphs with average degree at most four

详细信息    查看全文

• 作者：Tao Wang ; ^{wangtao@henu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; ^{iwangtao8@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 October 2016
• 年：2016
• 卷：339
• 期：10
• 页码：2581-2591
• 全文大小：412 K

文摘

A graph 624aca45dc86162fa7dfa200b5" title="Click to view the MathML source">H$H$ is said to be light   in a family G$\mathfrak{G}$ of graphs if at least one member of G$\mathfrak{G}$ contains a copy of 624aca45dc86162fa7dfa200b5" title="Click to view the MathML source">H$H$ and there exists an integer λ(H,G)$\lambda (H,\mathfrak{G})$ such that each member G$G$ of G$\mathfrak{G}$ with a copy of 624aca45dc86162fa7dfa200b5" title="Click to view the MathML source">H$H$ also has a copy 62afe60bd19aa69e3" title="Click to view the MathML source">K$K$ of 624aca45dc86162fa7dfa200b5" title="Click to view the MathML source">H$H$ such that deg_G(v)≤λ(H,G)${deg}_G\left(v\right)\le \lambda (H,\mathfrak{G})$ for all v∈V(K)$v\in V\left(K\right)$. In this paper, we study the light graphs in the class of graphs with small average degree, including the plane graphs with some restrictions on girth.

We proved that:

bel">1.

If G$G$ is a graph with δ(G)=2$\delta \left(G\right)=2$, average degree less than $\frac{14}{5}$ and without (2,2,∞)$(2,2,\infty )$-triangles, then G$G$ has one of the following configurations: a (2,2,13⁻,2)$(2,2,13^{-},2)$-path, a (2,3⁻,3⁻)$(2,3^{-},3^{-})$-path and a (4;2,2,2,3⁻)$(4;2,2,2,3^{-})$-star.

bel">2.

If G$G$ is a plane graph with δ(G)≥2$\delta \left(G\right)\ge 2$ and face size at least 7$7$, then G$G$ has a (2,2,5⁻)$(2,2,5^{-})$-path, or a (2,5⁻,2)$(2,5^{-},2)$-path or a 62893" title="Click to view the MathML source">(3,3,2,3)$(3,3,2,3)$-path.

bel">3.

If G$G$ is a graph with δ(G)=2$\delta \left(G\right)=2$, average degree less than 628dc746c5d" title="Click to view the MathML source">3$3$ and without (2,2,∞)$(2,2,\infty )$-triangles, then G$G$ has one of the following configurations: a (2,3⁻,3⁻)$(2,3^{-},3^{-})$-path, a (2,2,∞,2)$(2,2,\infty ,2)$-path, a (2,2,4,3)$(2,2,4,3)$-path, a (4;2,2,2,6⁻)$(4;2,2,2,6^{-})$-star, a (4;2,2,3,5⁻)$(4;2,2,3,5^{-})$-star, a (4;2,3,3,3)$(4;2,3,3,3)$-star, a (5;2,2,2,2,2)$(5;2,2,2,2,2)$-star and a (5;2,2,2,2,3)$(5;2,2,2,2,3)$-star.

bel">4.

If G$G$ is a graph with δ(G)=2$\delta \left(G\right)=2$, average degree less than 628dc746c5d" title="Click to view the MathML source">3$3$ and without (2,2,∞)$(2,2,\infty )$-triangles, then G$G$ has one of the following configurations: a (2,3⁻,3⁻)$(2,3^{-},3^{-})$-path, a (2,2,∞,2)$(2,2,\infty ,2)$-path, a (2,2,4,3)$(2,2,4,3)$-path, a (4;2,2,2,6⁻)$(4;2,2,2,6^{-})$-star, a (2,4,3,2)$(2,4,3,2)$-path, a (2,4,3)$(2,4,3)$-triangle, a (5;2,2,2,2,2)$(5;2,2,2,2,2)$-star and a (5;2,2,2,2,3)$(5;2,2,2,2,3)$-star.

bel">5.

If G$G$ is a graph with δ(G)≥2$\delta \left(G\right)\ge 2$ and average degree less than $\frac{10}{3}$, then G$G$ has one of the following configurations: a (2,2,∞)$(2,2,\infty )$-path, a (2,3,6⁻)$(2,3,6^{-})$-path, a (3,3,3)$(3,3,3)$-path, a (2,4,3⁻)$(2,4,3^{-})$-path and a 62" class="mathmlsrc">62.gif&_user=111111111&_pii=S0012365X16301170&_rdoc=1&_issn=0012365X&md5=2960aa80e6da78094980f99e8f4d7e25" title="Click to view the MathML source">(2,9⁻,2)-path.

bel">6.

If G$G$ is a graph with δ(G)=3$\delta \left(G\right)=3$ and average degree less than 4$4$, then G$G$ contains a (4⁻,3,7⁻)$(4^{-},3,7^{-})$-path, or a (5,3,5)$(5,3,5)$-path or a (5,3,6)$(5,3,6)$-path.

bel">7.

If G$G$ is a triangle-free normal plane map, then it contains one of the following configurations: a (3,3,3)$(3,3,3)$-path, a (3,3,4)$(3,3,4)$-path, a (3,3,5,3)$(3,3,5,3)$-path, a 625611ebc1e1b" title="Click to view the MathML source">(4,3,4)$(4,3,4)$-path, a 6226649251f30088e1f1a0cb" title="Click to view the MathML source">(4,3,5)$(4,3,5)$-path, a (5,3,5)$(5,3,5)$-path, a (5,3,6)$(5,3,6)$-path and a (3,4,3)$(3,4,3)$-path.