Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Connected [1,2]-Sets in Graphs
verfasst von : Chao Zhang, Chengye Zhao
Erschienen in: Theoretical Computer Science
Verlag: Springer Singapore
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A subset \(S \subseteq V(G)\) in a graph \(G=(V,E)\) is a connected [j, k]-set, if it satisfies that G[S] is a connected subgraph of G and every vertex \(v \in V \setminus S\), \(j \le |N(v) \cap S| \le k\) for non-negative integers \(j<k\). In this paper, we study the connected [1, 2]-domination number of graph G, which denoted \(\gamma _{c[1,2]}(G)\). We discussed the graphs with \(\gamma _{c[1,2]}(G)=n\) and the graphs with \(\gamma _{c[1,2]}(G)=\gamma _c(G)\). In the end, the CONNECTED [1, 2]-SET Problem has been proved to be NP-complete for bipartite graphs.