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

Zheng, 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 -