论文标题
循环图的盒装$ g_k^d $
Boxicity of Circulant Graph $G_k^d$
论文作者
论文摘要
The boxicity of a graph $G$, denoted by $box(G)$, is the least positive integer $\ell$ such that $G$ can be isomorphic to the intersection graph of a family of boxes in Euclidean $\ell$-space, where box in an Euclidean $\ell$-space is the Cartesian product of $\ell$ closed intervals on the real line.让$ k $和$ d $是两个带有$ k \ geq 2d $的正整数。循环图$ g_k^d $是带有顶点set $ v（g_k^d）= \ {a_0，a_1，\ ldots的图形\ d \ leq | i-j | \ leq k-d \} $。表示$χ（g）$图形$ g $的色数。在\ cite {aki} akira kamibeppu中证明了某些类别的循环图$ g_k^d $的$ box（g_k^d）\ leqχ（g_k^d）$，并提出了一个问题，即所有循环图都同样的结果。在此简短说明中，我们证明了$ box（g_k^d）\ leqχ（g_k^d）$，对于所有$ k $，$ k $ at in $ k \ geq 2d $。其中包括所有循环图$ g_k^d $。我们的证明非常简单且简短。这个答案上述问题。
The boxicity of a graph $G$, denoted by $box(G)$, is the least positive integer $\ell$ such that $G$ can be isomorphic to the intersection graph of a family of boxes in Euclidean $\ell$-space, where box in an Euclidean $\ell$-space is the Cartesian product of $\ell$ closed intervals on the real line. Let $k$ and $d$ be two positive integers with $k\geq 2d$. The circulant graph $G_k^d$ is the graph with vertices set $V(G_k^d)=\{a_0, a_1,\ldots, a_{k-1}\}$ and edge set $E(G_k^d)=\{a_i a_j | \ d\leq |i-j|\leq k-d\}$. Denote $χ(G)$ the chromatic number of a graph $G$. In \cite{Aki} Akira Kamibeppu proved that $box(G_k^d)\leq χ(G_k^d)$ for some class of circulant graph $G_k^d$ and raised the question that the same result holds for all circulant graph. In this short note, we prove that $box(G_k^d)\leq χ(G_k^d)$, for all $k$ and $d$ with $k\geq 2d$. This include all circulant graph $G_k^d$. Our proof is very simple and short. This answer the above question.
