Domination in 4-regular Knödel graphs
A subset D of vertices of a graph G is a dominating set if for each u ∈ V(G) ∖ D, u is adjacent to some vertex v ∈ D. The domination number, γ(G) of G, is the minimum cardinality of a dominating set of G. For an even integer n ≥ 2 and 1 ≤ Δ ≤ ⌊log2n⌋, a Knödel graph WΔ, n is a Δ-regular bipartite gr...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2018-08-01
|
| Series: | Open Mathematics |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/math-2018-0072 |
| _version_ | 1819122024309587968 |
|---|---|
| author | Mojdeh Doost Ali Musawi S.R. Nazari E. |
| author_facet | Mojdeh Doost Ali Musawi S.R. Nazari E. |
| author_sort | Mojdeh Doost Ali |
| collection | DOAJ |
| description | A subset D of vertices of a graph G is a dominating set if for each u ∈ V(G) ∖ D, u is adjacent to some vertex v ∈ D. The domination number, γ(G) of G, is the minimum cardinality of a dominating set of G. For an even integer n ≥ 2 and 1 ≤ Δ ≤ ⌊log2n⌋, a Knödel graph WΔ, n is a Δ-regular bipartite graph of even order n, with vertices (i, j), for i = 1, 2 and 0 ≤ j ≤ n/2 − 1, where for every j, 0 ≤ j ≤ n/2 − 1, there is an edge between vertex (1, j) and every vertex (2, (j+2k − 1) mod (n/2)), for k = 0, 1, ⋯, Δ − 1. In this paper, we determine the domination number in 4-regular Knödel graphs W4,n. |
| first_indexed | 2024-12-22T06:45:52Z |
| format | Article |
| id | doaj.art-23fb2bee4c4e4f23ba9ef114479cf77e |
| institution | Directory Open Access Journal |
| issn | 2391-5455 |
| language | English |
| last_indexed | 2024-12-22T06:45:52Z |
| publishDate | 2018-08-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Open Mathematics |
| spelling | doaj.art-23fb2bee4c4e4f23ba9ef114479cf77e2022-12-21T18:35:17ZengDe GruyterOpen Mathematics2391-54552018-08-0116181682510.1515/math-2018-0072math-2018-0072Domination in 4-regular Knödel graphsMojdeh Doost Ali0Musawi S.R.1Nazari E.2Department of Mathematics, University of Mazandaran, Babolsar, IranDepartment of Mathematics, Tafresh University, Tafresh, IranDepartment of Mathematics, Tafresh University, Tafresh, IranA subset D of vertices of a graph G is a dominating set if for each u ∈ V(G) ∖ D, u is adjacent to some vertex v ∈ D. The domination number, γ(G) of G, is the minimum cardinality of a dominating set of G. For an even integer n ≥ 2 and 1 ≤ Δ ≤ ⌊log2n⌋, a Knödel graph WΔ, n is a Δ-regular bipartite graph of even order n, with vertices (i, j), for i = 1, 2 and 0 ≤ j ≤ n/2 − 1, where for every j, 0 ≤ j ≤ n/2 − 1, there is an edge between vertex (1, j) and every vertex (2, (j+2k − 1) mod (n/2)), for k = 0, 1, ⋯, Δ − 1. In this paper, we determine the domination number in 4-regular Knödel graphs W4,n.https://doi.org/10.1515/math-2018-0072knödel graphdomination numberpigoenhole principal05c6905c30 |
| spellingShingle | Mojdeh Doost Ali Musawi S.R. Nazari E. Domination in 4-regular Knödel graphs Open Mathematics knödel graph domination number pigoenhole principal 05c69 05c30 |
| title | Domination in 4-regular Knödel graphs |
| title_full | Domination in 4-regular Knödel graphs |
| title_fullStr | Domination in 4-regular Knödel graphs |
| title_full_unstemmed | Domination in 4-regular Knödel graphs |
| title_short | Domination in 4-regular Knödel graphs |
| title_sort | domination in 4 regular knodel graphs |
| topic | knödel graph domination number pigoenhole principal 05c69 05c30 |
| url | https://doi.org/10.1515/math-2018-0072 |
| work_keys_str_mv | AT mojdehdoostali dominationin4regularknodelgraphs AT musawisr dominationin4regularknodelgraphs AT nazarie dominationin4regularknodelgraphs |