Ajou University repository

A tight bound for independent domination of cubic graphs without 4-cyclesoa mark
  • Cho, Eun Kyung ;
  • Choi, Ilkyoo ;
  • Kwon, Hyemin ;
  • Park, Boram
Citations

SCOPUS

5

Citation Export

Publication Year
2023-10-01
Publisher
John Wiley and Sons Inc
Citation
Journal of Graph Theory, Vol.104, pp.372-386
Keyword
cubic graphdomination numberindependent domination numberregular graph
Mesh Keyword
4-cycleCubic graphDominating setsDomination numberIndependent domination numberIndependent dominationsRegular graphsTight bound
All Science Classification Codes (ASJC)
Geometry and TopologyDiscrete Mathematics and Combinatorics
Abstract
Given a graph (Figure presented.), a dominating set of (Figure presented.) is a set (Figure presented.) of vertices such that each vertex not in (Figure presented.) has a neighbor in (Figure presented.). Let (Figure presented.) denote the minimum size of a dominating set of (Figure presented.). The independent domination number of (Figure presented.), denoted (Figure presented.), is the minimum size of a dominating set of (Figure presented.) that is also independent. We prove that if (Figure presented.) is a cubic graph without 4-cycles, then (Figure presented.), and the bound is tight. This result improves upon two results from two papers by Abrishami and Henning. Our result also implies that every cubic graph (Figure presented.) without 4-cycles satisfies (Figure presented.), which supports a question asked by O and West.
Language
eng
URI
https://dspace.ajou.ac.kr/dev/handle/2018.oak/33393
DOI
https://doi.org/10.1002/jgt.22968
Fulltext

Type
Article
Funding
We thank the referees for their careful reading and helpful comments that improved the readability of the paper. Eun\u2010Kyung Cho was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF\u20102020R1I1A1A01058587). Ilkyoo Choi was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF\u20102018R1D1A1B07043049), and also by the Hankuk University of Foreign Studies Research Fund. Boram Park was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF\u20102022R1F1A1069500).
Show full item record

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Park, Boram Image
Park, Boram박보람
Department of Mathematics
Read More

Total Views & Downloads

File Download

  • There are no files associated with this item.