Connected odd dominating sets in graphs | Zendy

Yair Caro | Zendy; William F. Klostermeyer | Zendy; Raphael Yuster | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Connected odd dominating sets in graphs

Author(s) -

Yair Caro,

William F. Klostermeyer,

Raphael Yuster

Publication year - 2005

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1276

Subject(s) - combinatorics , mathematics , dominating set , connected dominating set , maximal independent set , discrete mathematics , graph , simple graph , pathwidth , line graph , vertex (graph theory)

An odd dominating set of a simple, undirected graph G = (V, E) is a set of vertices D ⊆ V such that |N [v]∩D| ≡ 1 mod 2 for all vertices v ∈ V . It is known that every graph has an odd dominating set. In this paper we consider the concept of connected odd dominating sets. We prove that the problem of deciding if a graph has a connected odd dominating set is NP-complete. We also determine the existence or non-existence of such sets in several classes of graphs. Among other results, we prove there are only 15 grid graphs that have a connected odd dominating set. AMS subject classification index: primary 05C35.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research