论文标题
双顶点图的汉密尔顿和某些联接图的完整双顶点图
Hamiltonicity of the Double Vertex Graph and the Complete Double Vertex Graph of some Join Graphs
论文作者
论文摘要
令$ g $是订单$ n $的简单图表。 $ g $的双顶点图$ f_2（g）$是$ v（g）$的$ 2 $ -subsets的图形，如果它们的对称差为$ g $，则两个顶点在$ f_2（g）$中相邻。该图的概括是$ g $的完整双顶点图$ m_2（g）$，定义为$ v（g）$的$ 2 $ -multisubsets的图形，如果它们的对称差异（作为multisets）是$ g $ g $ g $ g $ g $ g $ g $。在本文中，我们展示了一个无限的图表（包含哈密顿量和非哈米尔顿图），其中$ f_2（g）$和$ m_2（g）$是哈密顿人。该图家族是一组JOIN图$ g = g_1 + g_2 $，其中$ g_1 $和$ g_2 $分别为$ m \ geq 1 $和$ n \ geq 2 $，$ g_2 $具有汉密尔顿路径。对于这个图形家庭，我们表明，如果$ m \ leq 2n $，则$ f_2（g）$是汉密尔顿人，如果$ m \ m \ leq 2（n-1）$，则$ m_2（g）$是汉密尔顿人。
Let $G$ be a simple graph of order $n$. The double vertex graph $F_2(G)$ of $G$ is the graph whose vertices are the $2$-subsets of $V(G)$, where two vertices are adjacent in $F_2(G)$ if their symmetric difference is a pair of adjacent vertices in $G$. A generalization of this graph is the complete double vertex graph $M_2(G)$ of $G$, defined as the graph whose vertices are the $2$-multisubsets of $V(G)$, and two of such vertices are adjacent in $M_2(G)$ if their symmetric difference (as multisets) is a pair of adjacent vertices in $G$. In this paper we exhibit an infinite family of graphs (containing Hamiltonian and non-Hamiltonian graphs) for which $F_2(G)$ and $M_2(G)$ are Hamiltonian. This family of graphs is the set of join graphs $G=G_1 + G_2$, where $G_1$ and $G_2$ are of order $m\geq 1$ and $n\geq 2$, respectively, and $G_2$ has a Hamiltonian path. For this family of graphs, we show that if $m\leq 2n$ then $F_2(G)$ is Hamiltonian, and if $m\leq 2(n-1)$ then $M_2(G)$ is Hamiltonian.
