论文标题

笛卡尔产品图的哈密顿和$ 1 $ tough属性之间的关系

The relation between Hamiltonian and $1$-tough properties of the Cartesian product graphs

论文作者

Kao, Louis, Weng, Chih-wen

论文摘要

汉密尔顿性与图形韧性之间的关系是一个长期存在的研究问题。论文研究笛卡尔产品图的Hamiltonicity $ G_1 \ Square G_2 $ g_2 $ $ g_1 $和$ g_2 $满足满足$ g_1 $的$ g_1 $是可追溯的,并且$ g_2 $与路径因子连接。令PN为订单$ n $,$ h $的路径为连接的两部分图。对于$ n $的某些要求,我们表明以下三个语句等效:(i)$ p_n \ square h $是汉密尔顿人; (ii)$ p_n \ square h $ as $ 1 $ -tough; (iii)$ h $有一个路径因素。

The relation between Hamiltonicity and toughness of a graph is a long standing research problem. The paper studies the Hamiltonicity of the Cartesian product graph $G_1\square G_2$ of graphs $G_1$ and $G_2$ satisfying that $G_1$ is traceable and $G_2$ is connected with a path factor. Let Pn be the path of order $n$ and $H$ be a connected bipartite graph. With certain requirements of $n$, we show that the following three statements are equivalent: (i) $P_n\square H$ is Hamiltonian; (ii) $P_n\square H$ is $1$-tough; and (iii) $H$ has a path factor.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源