Trees with No Locating Roman Domination Critical Vertices
- PDF / 299,396 Bytes
- 8 Pages / 595.276 x 790.866 pts Page_size
- 5 Downloads / 143 Views
(0123456789().,-volV)(0123456789().,-volV)
RESEARCH PAPER
Trees with No Locating Roman Domination Critical Vertices Hadi Rahbani1 • Ali Taherifar1 • Nader Jafari Rad2 Received: 28 March 2020 / Accepted: 30 October 2020 Shiraz University 2020
Abstract A Roman dominating function (or just RDF) on a graph G ¼ ðV; EÞ is a function f : V ! f0; 1; 2g satisfying the condition that every vertex u for which f ðuÞ ¼ 0 is adjacent to at least one vertex v for which f ðvÞ ¼ 2. The weight of an P RDF f is the value f ðVðGÞÞ ¼ u2VðGÞ f ðuÞ. An RDF f can be represented as f ¼ ðV0 ; V1 ; V2 Þ, where Vi ¼ fv 2 V : f ðvÞ ¼ ig for i ¼ 0; 1; 2. An RDF f ¼ ðV0 ; V1 ; V2 Þ is called a locating Roman dominating function (or just LRDF) if NðuÞ \ V2 6¼ NðvÞ \ V2 for any pair u, v of distinct vertices of V0 . The locating Roman domination number cLR ðGÞ is the minimum weight of an LRDF of G. A vertex v of a graph G is called a locating Roman domination critical vertex (or just cLR critical vertex) if cLR ðG vÞ\cLR ðGÞ. In this paper, we characterize all trees with no cLR critical vertices. Keywords Roman domination number Locating domination number Locating Roman domination number AMS Subject Classification 05C69
1 Introduction In this paper, we continue the study of a variant of Roman domination, namely, locating Roman domination. We first present some necessary terminology and notations. For notation and graph theory terminology not given here, we follow Haynes et al. (1998). We consider finite, undirected, and simple graphs G with vertex set V ¼ VðGÞ and edge set E ¼ EðGÞ. The number of vertices jVðGÞj of G is called the order of G and is denoted by n ¼ nðGÞ: The open neighborhood of a vertex v2V is NðvÞ ¼ NG ðvÞ ¼ fu 2 V j uv 2 Eg, and the degree of v, denoted by G ðvÞ, (or just ðvÞ) is the cardinality of its open neighborhood. A leaf of a graph G is a vertex of degree one, while a support vertex of G is a vertex adjacent to a leaf. A strong support vertex is a support vertex adjacent to
& Ali Taherifar [email protected] Hadi Rahbani [email protected] Nader Jafari Rad [email protected] 1
Department of Mathematics, Yasouj University, Yasouj, Iran
2
Department of Mathematics, Shahed University, Tehran, Iran
at least two leaves. We denote the set of all support vertices of G by S(G) and the set of leaves by L(G). We denote ‘ðGÞ ¼ jLðGÞj and sðGÞ ¼ jSðGÞj. We also denote by L(x) the set of leaves adjacent to a support vertex x, and denote ‘x ¼ jLðxÞj. An edge incident with a leaf is called a pendant edge. The subgraph induced in G by a subset of vertices S is denoted G[S]. A subset S V is a dominating set of G if every vertex in V S has a neighbor in S. The domination number cðGÞ is the minimum cardinality of a dominating set of G. A locating dominating set L VðGÞ is a dominating set of G such that for every two vertices u and v in VðGÞ L, NðuÞ \ S 6¼ NðvÞ \ S: The minimum size of a locating dominating set in a graph G is the locating domination number of G, denoted cL ðGÞ. The study of locating domina
Data Loading...
