J. Korean Math. Soc. 2011; 48(4): 691-702
Printed July 1, 2011
https://doi.org/10.4134/JKMS.2011.48.4.691
Copyright © The Korean Mathematical Society.
Boram Park and Yoshio Sano
Seoul National University, National Institute of Informatics
The competition graph of a digraph $D$ is a graph which has the same vertex set as $D$ and has an edge between $x$ and $y$ if and only if there exists a vertex $v$ in $D$ such that $(x,v)$ and $(y,v)$ are arcs of $D$. For any graph $G$, $G$ together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number $k(G)$ of a graph $G$ is defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition number $k(G)$ for a graph $G$ and it has been one of important research problems in the study of competition graphs. In this paper, we compute the competition numbers of Hamming graphs with diameter at most three.
Keywords: competition graph, competition number, edge clique cover, Hamming graph
MSC numbers: Primary 05C99
2005; 42(6): 1251-1264
© 2022. The Korean Mathematical Society. Powered by INFOrang Co., Ltd