# Traceability in $\{{K}_{1,4},{K}_{1,4}+e\}$-free graphs

Czechoslovak Mathematical Journal (2019)

- Volume: 69, Issue: 2, page 431-442
- ISSN: 0011-4642

## Access Full Article

top## Abstract

top## How to cite

topZheng, Wei, and Wang, Ligong. "Traceability in $\lbrace K_{1,4},K_{1,4}+e\rbrace $-free graphs." Czechoslovak Mathematical Journal 69.2 (2019): 431-442. <http://eudml.org/doc/294399>.

@article{Zheng2019,

abstract = {A graph $G$ is called $\lbrace H_1,H_2, \dots ,H_k\rbrace $-free if $G$ contains no induced subgraph isomorphic to any graph $H_i$, $1\le i\le k$. We define \[\sigma \_k= \min \biggl \lbrace \sum \_\{i=1\}^k d(v\_i) \colon \lbrace v\_1, \dots ,v\_k\rbrace \ \text\{is an independent set of vertices in\}\ G \biggr \rbrace .\]
In this paper, we prove that (1) if $G$ is a connected $\lbrace K_\{1,4\},K_\{1,4\}+e\rbrace $-free graph of order $n$ and $\sigma _3(G)\ge n-1$, then $G$ is traceable, (2) if $G$ is a 2-connected $\lbrace K_\{1,4\},K_\{1,4\}+e\rbrace $-free graph of order $n$ and $|N(x_1)\cup N(x_2)|+|N(y_1)\cup N(y_2)|\ge n-1$ for any two distinct pairs of non-adjacent vertices $\lbrace x_1,x_2\rbrace $, $\lbrace y_1,y_2\rbrace $ of $G$, then $G$ is traceable, i.e., $G$ has a Hamilton path, where $K_\{1,4\}+e$ is a graph obtained by joining a pair of non-adjacent vertices in a $K_\{1,4\}$.},

author = {Zheng, Wei, Wang, Ligong},

journal = {Czechoslovak Mathematical Journal},

keywords = {$\lbrace K_\{1,4\},K_\{1,4\}+e\rbrace $-free graph; neighborhood union; traceable},

language = {eng},

number = {2},

pages = {431-442},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {Traceability in $\lbrace K_\{1,4\},K_\{1,4\}+e\rbrace $-free graphs},

url = {http://eudml.org/doc/294399},

volume = {69},

year = {2019},

}

TY - JOUR

AU - Zheng, Wei

AU - Wang, Ligong

TI - Traceability in $\lbrace K_{1,4},K_{1,4}+e\rbrace $-free graphs

JO - Czechoslovak Mathematical Journal

PY - 2019

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 69

IS - 2

SP - 431

EP - 442

AB - A graph $G$ is called $\lbrace H_1,H_2, \dots ,H_k\rbrace $-free if $G$ contains no induced subgraph isomorphic to any graph $H_i$, $1\le i\le k$. We define \[\sigma _k= \min \biggl \lbrace \sum _{i=1}^k d(v_i) \colon \lbrace v_1, \dots ,v_k\rbrace \ \text{is an independent set of vertices in}\ G \biggr \rbrace .\]
In this paper, we prove that (1) if $G$ is a connected $\lbrace K_{1,4},K_{1,4}+e\rbrace $-free graph of order $n$ and $\sigma _3(G)\ge n-1$, then $G$ is traceable, (2) if $G$ is a 2-connected $\lbrace K_{1,4},K_{1,4}+e\rbrace $-free graph of order $n$ and $|N(x_1)\cup N(x_2)|+|N(y_1)\cup N(y_2)|\ge n-1$ for any two distinct pairs of non-adjacent vertices $\lbrace x_1,x_2\rbrace $, $\lbrace y_1,y_2\rbrace $ of $G$, then $G$ is traceable, i.e., $G$ has a Hamilton path, where $K_{1,4}+e$ is a graph obtained by joining a pair of non-adjacent vertices in a $K_{1,4}$.

LA - eng

KW - $\lbrace K_{1,4},K_{1,4}+e\rbrace $-free graph; neighborhood union; traceable

UR - http://eudml.org/doc/294399

ER -

## References

top- Bauer, D., Fan, G., Veldman, H. J., 10.1016/0012-365X(91)90468-H, Discrete Math. 96 (1991), 33-49. (1991) Zbl0741.05039MR1139438DOI10.1016/0012-365X(91)90468-H
- Bondy, J. A., Murty, U. S. R., 10.1007/978-1-349-03521-2, American Elsevier Publishing, New York (1976). (1976) Zbl1226.05083MR0411988DOI10.1007/978-1-349-03521-2
- Duan, F., Wang, G. P., 10.1007/s10114-012-0459-7, Acta Math. Sin., Engl. Ser. 28 (2012), 2501-2506. (2012) Zbl1259.05091MR2995196DOI10.1007/s10114-012-0459-7
- Li, R., 10.1016/j.disc.2004.05.014, Discrete Math. 287 (2004), 69-76. (2004) Zbl1052.05505MR2094057DOI10.1016/j.disc.2004.05.014
- Li, R., Schelp, R. H., 10.1016/S0012-365X(01)00141-8, Discrete Math. 245 (2002), 195-202. (2002) Zbl0995.05086MR1887938DOI10.1016/S0012-365X(01)00141-8
- Lin, H., Wang, J., 10.1016/j.disc.2007.08.051, Discrete Math. 308 (2008), 4280-4285. (2008) Zbl1235.05075MR2427760DOI10.1016/j.disc.2007.08.051

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.