On Irregular Domination in Graphs
摘要
A set S of vertices in a connected graph G is an irregular dominating set if the vertices of S can be labeled with distinct positive integers in such a way that for every vertex v of G, there is a vertex \(u \in S\) such that the distance from u to v is the label assigned to u. For a connected graph G possessing an irregular dominating set, the irregular domination number of G is the minimum cardinality of an irregular dominating set in G. An irregular dominating set S in a connected graph G is minimal if for every vertex \(u \in S\) , there is a vertex v of G such that v is dominated by u only. A graph H is an irregular domination graph if there exists a graph G with a minimal irregular dominating set S such that H is isomorphic to the subgraph \(G[S]\) of G induced by S. All trees possessing an irregular dominating set are determined. For each integer \(r \ge 3\) , it is shown that there are r-regular graphs of diameter 3 possessing an irregular dominating set. It is shown that every connected graph with irregular domination number 3 is an irregular domination graph. Open questions and conjectures are also presented in this area of research.