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

0

Citation Export

Publication Year
2023-10-01
Journal
Journal of Graph Theory
Publisher
John Wiley and Sons Inc
Citation
Journal of Graph Theory, Vol.104 No.2, 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.
ISSN
1097-0118
Language
eng
URI
https://aurora.ajou.ac.kr/handle/2018.oak/33393
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85158066980&origin=inward
DOI
https://doi.org/2-s2.0-85158066980
Journal URL
http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1097-0118
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.