Domination in 4-regular Knödel graphs
| Autor: | Seyed Reza Musawi, Esmaeil Nazari, Doost Ali Mojdeh |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
021103 operations research
domination number General Mathematics 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology 01 natural sciences Combinatorics 05c69 010201 computation theory & mathematics knödel graph QA1-939 pigoenhole principal 05c30 Mathematics |
| Zdroj: | Open Mathematics, Vol 16, Iss 1, Pp 816-825 (2018) |
| ISSN: | 2391-5455 |
| DOI: | 10.1515/math-2018-0072 |
| Popis: | 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 ≤ Δ ≤ ⌊log2 n⌋, 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+2 k − 1) mod (n/2)), for k = 0, 1, ⋯, Δ − 1. In this paper, we determine the domination number in 4-regular Knödel graphs W 4,n . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|