Domination parameters in Mycielski graphs
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this paper, we consider several domination parameters like perfect domination number, locating-domination number, open-locating-domination number, etc.~in the Mycielski graph $M(G)$ of a graph $G$. We found upper bounds for locating-domination number of $M(G)$ and computational formulae for perfect locating-domination number and open locating-domination number of $M(G)$. We also showed that the perfect domination number of $M(G)$ is at least that of $G$ plus $1$ and that for each positive integer $n$, there exists a graph $G_n$ such that the perfect domination number of $M(G_n)$ is equal to that of $G_n$ plus $n$.
Abstract
In this paper, we consider several domination parameters like perfect domination number, locating-domination number, open-locating-domination number, etc.~in the Mycielski graph $M(G)$ of a graph $G$. We found upper bounds for locating-domination number of $M(G)$ and computational formulae for perfect locating-domination number and open locating-domination number of $M(G)$. We also showed that the perfect domination number of $M(G)$ is at least that of $G$ plus $1$ and that for each positive integer $n$, there exists a graph $G_n$ such that the perfect domination number of $M(G_n)$ is equal to that of $G_n$ plus $n$.
참고문헌 (10)
- Gerard J. Chang, "Circular chromatic numbers of Mycielski's graphs", Discrete Mathematics, 205(1-3), pp.23~37 (1999), Elsevier BV[DOI]
- X. Chen, "Domination parameters in Mycielski graphs", Util. Math, 71, pp.235~244 (2006)
- Genghua Fan, "Circular Chromatic Number and Mycielski Graphs", Combinatorica, 24(1), pp.127~135 (2004), Springer Science and Business Media LLC[DOI]
- T. W. Haynes, "Fundamentals of domination in graphs" (1998), Marcel Dekker, Inc
- Michael Larsen, "The fractional chromatic number of mycielski's graphs", Journal of Graph Theory, 19(3), pp.411~416 (1995), Wiley[DOI]
- Wensong Lin, "Several parameters of generalized Mycielskians", Discrete Applied Mathematics, 154(8), pp.1173~1182 (2006), Elsevier BV[DOI]
- Daphne Der-Fen Liu, "Circular chromatic number for iterated Mycielski graphs", Discrete Mathematics, 285(1-3), pp.335~340 (2004), Elsevier BV[DOI]
- D. A. Mojdeh, "On domination and its forcing in Mycielski’s graphs", Sci. Iran, 15(2), pp.218~222 (2008)
- Jan Mycielski, "Sur le coloriage des graphs", Colloquium Mathematicum, 3(2), pp.161~162 (1955), Institute of Mathematics, Polish Academy of Sciences[DOI]
- Claude Tardif, "Fractional chromatic numbers of cones over graphs", Journal of Graph Theory, 38(2), pp.87~94 (2001), Wiley[DOI]