DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in press

Authors:

J. Huang

Jia Huang

University of Nebraska at Kearney

email: huangj2@unk.edu

Title:

Dissociation in circulant graphs and integer distance graphs

PDF

Source:

Discussiones Mathematicae Graph Theory

Received: 2023-07-06 , Revised: 2024-09-23 , Accepted: 2024-09-23 , Available online: 2024-10-03 , https://doi.org/10.7151/dmgt.2563

Abstract:

A dissociation set of a graph $G$ is a set of vertices which induces a subgraph of $G$ with maximum degree at most $1$, or equivalently, a set of vertices whose complement in $G$ is a $3$-path vertex cover (intersecting every $3$-path of $G$). The maximum cardinality of a dissociation set of $G$ is called the dissociation number of $G$. We study the dissociation number of a circulant graph (a Cayley graph of the group $\mathbb{Z}_n$) and generalize this concept to the dissociation ratio of an integer distance graph (a Cayley graph of the group $\mathbb{Z}$).

Keywords:

dissociation number, dissociation ratio, circulant graph, integer distance graph

References:

  1. V.E. Alekseev, R. Boliac, D.V. Korobitsyn and V.V. Lozin, NP-hard graph problems and boundary classes of graphs, Theoret. Comput. Sci. 389 (2007) 219–236.
    https://doi.org/10.1016/j.tcs.2007.09.013
  2. B. Brešar, M. Jakovac, J. Katrenič, G. Semanišin and A. Taranenko, On the vertex $k$-path cover, Discrete Appl. Math. 161 (2013) 1943–1949.
    https://doi.org/10.1016/j.dam.2013.02.024
  3. B. Brešar, F. Kardoš, J. Katrenič and G. Semanišin, Minimum $k$-path vertex cover, Discrete Appl. Math. 159 (2011) 1189–1195.
    https://doi.org/10.1016/j.dam.2011.04.008
  4. Cs. Bujtás, M. Jakovac and Zs. Tuza, The $k$-path vertex cover: general bounds and chordal graphs, Networks 80 (2022) 63–76.
    https://doi.org/10.1002/net.22079
  5. K. Cameron and P. Hell, Independent packings in structured graphs, Math. Program. 105 (2006) 201–213.
    https://doi.org/10.1007/s10107-005-0649-5
  6. J.M. Carraher, D. Galvin, S.G. Hartke, A.J. Radcliffe and D. Stolee, On the independence ratio of distance graphs, Discrete Math. 339 (2016) 3058–3072.
    https://doi.org/10.1016/j.disc.2016.05.018
  7. N. Frankl, A. Kupavskii and A. Sagdeev, Solution to a conjecture of Schmidt and Tuller on one-dimensional packings and coverings, Proc. Amer. Math. Soc. 151 (2023) 2353–2362.
    https://doi.org/10.1090/proc/16254
  8. J. Huang, Domination ratio of integer distance digraphs, Discrete Appl. Math. 262 (2019) 104–115.
    https://doi.org/10.1016/j.dam.2019.03.001
  9. J. Huang, Domination ratio of a family of integer distance digraphs with arbitrary degree, Discrete Appl. Math. 317 (2022) 1–9.
    https://doi.org/10.1016/j.dam.2022.04.011
  10. D.D.-F. Liu, From rainbow to the lonely runner: a survey on coloring parameters of distance graphs, Taiwanese J. Math. 12 (2008) 851–871.
    https://doi.org/10.11650/twjm/1500404981
  11. E.A. Monakhova, A survey on undirected circulant graphs, Discrete Math. Algorithms Appl. 4 (2012) 1250002.
    https://doi.org/10.1142/S1793830912500024
  12. D.J. Newman, Complements of finite sets of integers, Michigan Math. J. 14 (1967) 481–486.
    https://doi.org/10.1307/mmj/1028999851
  13. Y. Orlovich, A. Dolgui, G. Finke, V. Gordon and F. Werner, The complexity of dissociation set problems in graphs, Discrete Appl. Math. 159 (2011) 1352–1366.
    https://doi.org/10.1016/j.dam.2011.04.023
  14. C.H. Papadimitriou and M. Yannakakis, The complexity of restricted spanning tree problems, J. ACM 29 (1982) 285–309.
    https://doi.org/10.1145/322307.322309
  15. W.M. Schmidt and D.M. Tuller, Covering and packing in $\Bbb Z^n$ and $\Bbb R^n$ (I), Monatsh. Math. 153 (2008) 265–281.
    https://doi.org/10.1007/s00605-007-0500-6
  16. W.M. Schmidt and D.M. Tuller, Covering and packing in $\Bbb Z^n$ and $\Bbb R^n$ (II), Monatsh. Math. 160 (2010) 195–210.
    https://doi.org/10.1007/s00605-009-0099-x
  17. J. Tu, L. Zhang and J. Du, On the maximum number of maximum dissociation sets in trees with given dissociation number, Discrete Math. 347 (2024) 113910.
    https://doi.org/10.1016/j.disc.2024.113910
  18. J. Tu, Z. Zhang and Y. Shi, The maximum number of maximum dissociation sets in trees, J. Graph Theory 96 (2021) 472–489.
    https://doi.org/10.1002/jgt.22627
  19. M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput. 10 (1981) 310–327.
    https://doi.org/10.1137/0210022
Close