论文标题
笛卡尔产品图的哈密顿和$ 1 $ tough属性之间的关系
The relation between Hamiltonian and $1$-tough properties of the Cartesian product graphs
论文作者
论文摘要
汉密尔顿性与图形韧性之间的关系是一个长期存在的研究问题。论文研究笛卡尔产品图的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.