Akademik Veri Yönetim Sistemi
6th International Conference on Engineering and Applied Natural Sciences ICEANS 2025, Konya, Türkiye, 23 - 24 Haziran 2025, ss.26, (Özet Bildiri)
In this study, a novel graph-theoretical concept called k-domination connectivity is introduced, combining the well-established notions of domination and connectivity in graph theory. While each of these concepts has been extensively investigated independently—with domination theory boasting over 40 parameters and connectivity being a fundamental tool in the analysis of fault tolerance in networks—the combination of these two ideas into a unified invariant is innovative and offers new perspectives for analyzing structural robustness in complex systems.
The proposed k-domination connectivity number, denoted by 𝜅𝛾(𝑘)(𝐺), is defined for a connected graph 𝐺 = (𝑉,𝐸). For a given integer 𝑘 ≥ 1, a subset 𝑆 ⊆ 𝑉(𝐺) is considered such that 𝐺 − 𝑆 becomes disconnected and each connected component in 𝐺 − 𝑆 has domination number exactly equal to 𝑘. The minimum cardinality of such a set 𝑆 is the 𝑘-domination connectivity number of 𝐺. This invariant may have potential applications in areas like secure network design, fault-tolerant distributed systems, and VLSI circuit analysis, where both separation and control criteria are essential.
In this note, the authors focus on computing the 2-domination connectivity number 𝜅𝛾(𝑘)(𝐺) for two fundamental families of graphs: paths (𝑃𝑛) and cycles (𝐶𝑛). By carefully analyzing the structural decomposition of paths and cycles after the removal of certain vertices, it is demonstrated that:
•
For paths 𝑃ₙ with 𝑛 ≥ 9, the 2-domination connectivity number is given by 𝜅𝛾(2)(𝑃𝑛) = ⌊𝑛 / 7⌋.
•
For cycles 𝐶ₙ with 𝑛 ≥ 10, the corresponding value is 𝜅𝛾(2)(𝐶𝑛) = ⌈𝑛 / 7⌉.
The proofs involve decomposing the residual disconnected graphs into subpaths isomorphic to 𝑃₄,𝑃₅, or 𝑃₆, which are precisely those path graphs whose domination number is 2. A case-by-case analysis based on congruence classes modulo 7 is conducted to rigorously justify the results.
The work concludes with a discussion on possible extensions of the 𝑘-domination connectivity concept. Several open problems and directions are identified, such as computing 𝜅𝛾(𝑘)(𝐺) for other graph classes (e.g., complete graphs, interconnection networks like hypercubes or toroidal grids) and extending the definition to other domination variants—such as total domination connectivity, restrained domination connectivity, or Roman domination connectivity.
This study serves as an initial contribution to a new area of conditional connectivity measures, enriching both the theoretical and applied landscape of domination-based graph invariants.