Nonsplit domination number in vertex semi-middle graph

Let G(p, q) be a connected graph and Mv (G) be its corresponding vertex semi middle graph. A dominating set D⊆V[Mv (G)] is Nonsplit dominating set 〈V[Mv (G)]-D〉 is connected. The minimum size of D is called the Nonsplit domination number of Mv (G) and is denoted by γns [Mv (G)]. In this paper we obtain several results on Nonsplit domination number.

Illustrations explain the paper; they do not show study data.

AI-generated illustration

↗ Enlarge

Nonsplit Domination ConceptClose ×

AI-generated conceptual illustration (mathematical graph network of vertices and edges). It explains the idea and does not show study data.

Open full-size image ↗

Introduction

Domination is an area in graph theory with an extensive research activity. We consider simple, finite, undirected, non-trivial and connected graphs for our study. In literature, the concept of graph theory terminology not presented here can be found in Harary [1]. In a graph 𝐺, a set 𝐷⊆ 𝑉 is dominating set of 𝐺 if every vertex in 𝑉−𝐷 is adjacent to some vertex in 𝐷.

The domination number of a graph 𝐺 is the minimum size of 𝐷. Some studies on domination and other graph valued functions in graph theory were studied in [2-14, 16-24, 27-29]. The vertex semi middle graph 𝑀𝑣(𝐺) of a graph 𝐺 was studied in [25] and is defined as follows. The vertex semi-middle graph of a graph G, denoted by 𝑀𝑣(𝐺) is a planar graph whose vertex set is V(G)⋃E(G)⋃R(G) and two vertices of 𝑀𝑣(𝐺) are adjacent if and only if they corresponds to two adjacent edges of 𝐺 or one corresponds to a vertex and other to an edge incident with it or one corresponds to a vertex other to a region in which vertex lies on the region.

Let R′ = {r1 ′ } ⊆ V[𝑀𝑣(𝐺)] for the region set {r1, r2, … rm} of 𝐺. Let V′ = {v1 ′, r2 ′, v2 ′ , . . . eq ′ } ⊆ V[𝑀𝑣(𝐺)] for the vertex set {v1, v2, … vp} of 𝐺. Let E′ = {e1 ′ , e2 ′ } ⊆ V[𝑀𝑣(𝐺)] for the edge set {e1, e2, … eq} of 𝐺 such that V[𝑀𝑣(𝐺)] = V ′⋃ E′ ⋃ R′. The study of domination number of jump graph [15] motivated us to introduce nonsplit domination number in vertex semi middle graph. 2.

Preliminaries Theorem 2.1: [26] For the path 𝑃𝑛, 𝛾[𝑀𝑣(𝑃𝑛)] = 𝛾[𝐿(𝑃𝑛)] + 1. Theorem 2.2: [26] For the cycle 𝐶𝑛 , 𝑛≥4, 𝑛 3 + 2 𝑖𝑓 𝑛= 3𝑘, 𝑘≥2. 𝛾[𝑀𝑣(𝐶𝑛)] = { ⌈𝑛 3 + 1⌉ 𝑖𝑓 𝑛= 3𝑘+ 1 𝑜𝑟 𝑛= 3𝑘+ 2, 𝑘≥1. 𝑃 Theorem 2.3: [26] For any graph G, 𝛾[𝑀𝑣(𝐺)] ≥⌈ 1+∆(𝐺)⌉. Maths 2022; 7(4): 105-109 Niranjan KM Department of Mathematics, UBDT College of Engineering, Davangere, Karnataka, India Rajendra Prasad KC Department of Mathematics, Jain Institute of Technology, Davangere, Karnataka, India Venkanagouda M Goudar Department of Mathematics, Sri Siddhartha Institute of Technology, Tumkur, Karnataka, India Rajendra Prasad KC Department of Mathematics, Jain Institute of Technology, Davangere, Karnataka, India https://www.mathsjournal.com 3. Nonsplit domination number in vertex semi-middle graph A dominating set D of 𝑀𝑣(𝐺) is a nonsplit dominating set if 〈𝑉[𝑀𝑣(𝐺)] −𝐷〉 is connected.

The minimum cardinality of D is called nonsplit domination number of 𝑀𝑣(𝐺) and is denoted by 𝛾𝑛𝑠[𝑀𝑣(𝐺)]. A minimum nonsplit dominating set is denoted by 𝛾𝑛𝑠−𝑠𝑒𝑡. In the Fig 1, the nosplit dominating set of 𝑀𝑣(𝐺) is D = {3, 𝑟1 ′, 𝑟2 ′}, 𝛾𝑛𝑠[𝑀𝑣(𝐺)] = 3. 𝑛 Fig 1: The Graph 𝐺 and its 𝑀𝑣(𝐺) We begin with some observations. Observation 3.1 For the path 𝑃2, 𝛾𝑛𝑠[𝑀𝑣(𝑃2)] = 2.

↗ Enlarge

Figure 1Close ×

The Graph 𝐺 and its 𝑀𝑣(𝐺)

Open full-size image ↗

Original paper figureSource PDF · page 2 ↗

Observation 3.2 For any cycle 𝐶𝑛, 𝛾𝑛𝑠[𝑀𝑣(𝐶𝑛)] = 𝛾[𝑀𝑣(𝐶𝑛)]. Observation 3.3 For the path 𝑃𝑛, 𝑖[𝑀𝑣(𝑃𝑛)] = 𝛾[𝑀𝑣(𝑃𝑛)]. 4. Main Results Theorem 4.1: For the path 𝑃𝑛, 𝑛≥3, 𝛾𝑛𝑠[𝑀𝑣(𝑃𝑛)] = ⌊ 2⌋+ 1. Proof: Consider 𝐺= 𝑃𝑛 and 𝑉(𝑃𝑛) = {𝑣𝑖, 1 ≤𝑖≤𝑛} for 𝑛≥3.

Let D be the dominating set of 𝑀𝑣(𝑃𝑛). For 𝑃3, 𝑃5, D itself is a 𝛾𝑛𝑠−𝑠𝑒𝑡. Let D′ be the dominating set for 𝑃𝑛, 𝑛≠3,5 and define it as follows. ′ … … … 𝑣𝑛 ′, 𝑣4 ′, 𝑣2 𝐷′ = { 𝑟1 ′ 𝑖𝑓 𝑛= 2𝑙+ 1, 𝑙≥1. ′ 𝑖𝑓 𝑛= 2𝑙, 𝑙≥2. 𝑟1 ′, 𝑣4 ′, … … … 𝑣𝑛−1 ′, 𝑣2 𝑛 𝑛 Clearly, 〈𝑉[𝑀𝑣(𝑃𝑛) −𝐷′]〉is connected. Therefore |𝐷′| = ⌊ 2⌋+ 1.

It follows that 𝛾𝑛𝑠[𝑀𝑣(𝑃𝑛)] = ⌊ 2⌋+ 1. Theorem 4.2: For every graph 𝐺(𝑝, 𝑞), 𝛾𝑛𝑠[𝑀𝑣(𝐺)] ≥ 𝛾[𝑀𝑣(𝐺)]. Proof: Consider 𝑉[𝑀𝑣(𝐺)] = 𝑉′ ∪𝐸′ ∪𝑅′ and 𝐷= {𝑢𝑖 ′/ 𝑢𝑖 ′ ∈𝑉[𝑀𝑣(𝐺)]} be the dominating set of 𝑀𝑣(𝐺). Here we have to consider four cases.

Case 1: Let 𝑣𝑖be the non pendant vertex in 𝑃𝑛 then the corresponding vertex in 𝑀𝑣(𝐺) is 𝑣𝑖 ′. Consider 𝐺= 𝑃𝑛. By the Theorem 4.1, D is not non-split dominating set. Further, Consider D′ = D ∪ {𝑣𝑖 ′} such that 𝑉[𝑀𝑣(𝑃𝑛)] −𝐷′ is connected.

It follows that |D′| ≥ |D|. Hence 𝛾𝑛𝑠[𝑀𝑣(𝑃𝑛)] ≥ 𝛾[𝑀𝑣(𝑃𝑛)]. https://www.mathsjournal.com 𝑃 Case 2: Let G be a tree. By Case 1, it is obvious that, 𝛾𝑛𝑠[𝑀𝑣(𝑇)] ≥ 𝛾[𝑀𝑣(𝑇)]. Case 3: Let 𝐺= 𝐶𝑛.

By Observation 3.2, 𝛾𝑛𝑠[𝑀𝑣(𝐶𝑛)] = 𝛾[𝑀𝑣(𝐶𝑛)]. Thus, 𝑉[𝑀𝑣(𝐶𝑛) −𝐷] is connected by Theorem 2.2 and it follows. Case 4: Let G be any graph. By the Theorem 4.1, Observation 3.2 and Theorem 2.2, as a result, 𝛾𝑛𝑠[𝑀𝑣(𝐺)] ≥ 𝛾[𝑀𝑣(𝐺)].

From the above cases, we can say that 𝛾𝑛𝑠[𝑀𝑣(𝐺)] ≥ 𝛾[𝑀𝑣(𝐺)]. Theorem 4.3: For every graph 𝐺(𝑝, 𝑞), 𝛾𝑛𝑠[𝑀𝑣(𝐺)] ≥⌈ 1+∆(𝐺)⌉. Proof: From Theorem 2.3, 𝛾[𝑀𝑣(𝐺)] ≥⌈ 𝑃 1 + ∆(𝐺)⌉… … … . … . (1) 𝑃 By Theorem 4.2, 𝛾𝑛𝑠[𝑀𝑣(𝐺)] ≥ 𝛾[𝑀𝑣(𝐺)] … … … … . (2) We have, From equation (1) and equation (2), 𝛾𝑛𝑠[𝑀𝑣(𝐺)] ≥⌈ 1+∆(𝐺)⌉… … … . . … . (3) 𝑑𝑖𝑎𝑚(𝐺)+1 Theorem 4.4: Let 𝐺(𝑝, 𝑞) be a graph, 𝛾𝑛𝑠[𝑀𝑣(𝐺)] ≥⌈ 2 ⌉. Proof: Let 𝑆= {𝑒𝑘, 1 ≤𝑘≤𝑞} ⊆𝑉(𝐺) be the diametral path in G.

Clearly, |S| = diam(G). Consider D be the dominating set of 𝑀𝑣(𝐺). If 〈𝑉[𝑀𝑣(𝐺)] −𝐷〉 is connected, then D itself is a 𝛾𝑛𝑠−𝑠𝑒𝑡 of 𝑀𝑣(𝐺). Otherwise, at least one vertex exists with a maximum degree {𝑣𝑖 ′} ∈𝑉[𝑀𝑣(𝐺)] −𝐷 such that 〈𝑉[𝑀𝑣(𝐺)] −(𝐷∪{𝑣𝑖 ′}〉 has only one component.

It explicitly forms a γ – set of 𝑀𝑣(𝐺) that is non-split. Further, since S′⊆ V[𝑀𝑣(𝐺)] and D∪{𝑣𝑖 ′} is a 𝛾𝑛𝑠−𝑠𝑒𝑡 in 𝑀𝑣(𝐺). The diametral path includes at most 𝛾𝑛𝑠[𝑀𝑣(𝐺)] −1 edges connecting the neighbourhoods of the vertices of 𝑉[𝑀𝑣(𝐺)] −(𝐷∪{𝑣𝑖 𝑑𝑖𝑎𝑚(𝐺)+1 ′}). Hence 𝛾𝑛𝑠[𝑀𝑣(𝐺)] + 𝛾𝑛𝑠[𝑀𝑣(𝐺)] −1 ≥𝑑𝑖𝑎𝑚(𝐺).

Which gives 𝛾𝑛𝑠[𝑀𝑣(𝐺)] ≥⌈ 2 ⌉. Theorem 4.5: For every graph 𝐺(𝑝, 𝑞), 𝛾𝑛𝑠[𝑀𝑣(𝐺)] ≤𝑑𝑖𝑎𝑚(𝐺) + 𝛼0(𝐺). Proof: Let 𝛼0(𝐺) be the vertex covering number of 𝐺. Let 𝑉(𝐺) = {𝑣1, 𝑣2, … … 𝑣𝑛} ∃ 𝑣𝑖, 𝑣𝑗∈𝑉(𝐺) such that 𝐾= 𝑑(𝑣𝑖, 𝑣𝑗) = {𝑣1, 𝑣2, … … 𝑣𝑘} forms a diametral path in 𝐺.

Let 𝐷 be the 𝛾−𝑠𝑒𝑡 of 𝑀𝑣(𝐺). If 〈𝑉[𝑀𝑣(𝐺)] −𝐷〉 is connected then 〈𝐷〉 itself forms the 𝛾𝑛𝑠−𝑠𝑒𝑡 of 𝑀𝑣(𝐺). Clearly, |D| ≤ |K ∪ A|. It follows that 𝛾𝑛𝑠[𝑀𝑣(𝐺)] ≤𝑑𝑖𝑎𝑚(𝐺) + 𝛼0(𝐺).

Otherwise, there exists at least one vertex having maximum degree {𝑣𝑖 ′} ∈𝑉[𝑀𝑣(𝐺)] −𝐷 such that 〈𝑉[𝑀𝑣(𝐺)] −(𝐷∪{𝑣𝑖 ′}〉 has only one component. Clearly, it forms a 𝛾𝑛𝑠−𝑠𝑒𝑡 of 𝑀𝑣(𝐺). Since 𝑉[𝑀𝑣(𝐺)] −(𝐷∪{𝑣𝑖 ′}) includes diametral path. We have |𝑉[𝑀𝑣(𝐺)] −(𝐷∪ {𝑣𝑖 ′})| ≤|𝐾∪𝐴|.

Hence 𝛾𝑛𝑠[𝑀𝑣(𝐺)] ≤𝑑𝑖𝑎𝑚(𝐺) + 𝛼0(𝐺). Theorem 4.6: For every tree 𝑇, 𝛾[𝑀𝑣(𝑇)] = 𝑖[𝑀𝑣(𝑇)]. Proof: Suppose that the minimum vertex set is 𝐷⊆𝐸′(𝑇)⋃𝑟1 𝑛 ′ that is 𝑁(𝐷) = 𝑉[𝑀𝑣(𝑇)]. Hence D forms the γ - set in 𝑀𝑣(𝑇).

Clearly |𝐷| = 𝛾[𝑀𝑣(𝑇)] and also 〈𝐷〉is totally disconnected. Thus, 𝛾[𝑀𝑣(𝑇)] = 𝑖[𝑀𝑣(𝑇)]. Theorem 4.7: For the cycle 𝐶𝑛, i) 𝑖[𝑀𝑣(𝐶𝑛)] = ⌊ 2⌋+ 1 𝑖𝑓 4 ≤𝑛≤11. 𝑛 ii) 𝑖[𝑀𝑣(𝐶𝑛)] = ⌈ 3⌉+ 2 𝑖𝑓 𝑛≥12. Proof: Consider 𝐺= 𝐶𝑛 and 𝑉(𝐶𝑛) = {𝑣𝑖, 1 ≤𝑖≤𝑛} 𝑓𝑜𝑟 𝑛≥3.

Let 𝑒𝑖 ′, 𝑣𝑖 ′ ∈𝑉[𝑀𝑣(𝐶𝑛)]. Let the dominating set of 𝑀𝑣(𝐶𝑛) be 𝐷. Case 1: For 𝑛= 4,5,6,7,9 𝐷 itself is a 𝑖−𝑠𝑒𝑡. Otherwise, 𝐷 is not a independent dominating set for 𝑛= 8,10,11.

Let 𝐷′ be the set and define it as follows. https://www.mathsjournal.com ′ 𝑣𝑛 ′, 𝑒4 ′, 𝑒2 ′, … … 𝑒𝑛−2 𝐷′ = {𝑣1 ′ 𝑖𝑓 𝑛= 11. ′ … … 𝑒𝑛 ′ 𝑖𝑓 𝑛= 8, 10. 𝑟1 ′, 𝑟2 ′, 𝑒2 ′, 𝑒5 𝑛 𝑛 Clearly, 〈𝐷′〉 is totally disconnected and is 𝑖−𝑠𝑒𝑡 of 𝑀𝑣(𝐶𝑛). Hence |𝐷′| = ⌊ 2⌋+ 1. It follows that 𝑖[𝑀𝑣(𝐶𝑛)] = ⌊ 2⌋+ 1. Case 2: For 𝑛≥12, if 〈𝐷〉 is totally disconnected then 𝐷 itself is a 𝑖−𝑠𝑒𝑡 of 𝑀𝑣(𝐶𝑛).

Otherwise, we consider 𝐷′ = 𝐷∪𝑟2 𝑛 𝑛 ′ such that 𝐷′ is totally disconnected. It follows that |𝐷′| = ⌈ 3⌉+ 2. Hence 𝑖[𝑀𝑣(𝐶𝑛)] = ⌈ 3⌉+ 2. Theorem 4.8: For every graph 𝐺(𝑝, 𝑞), 𝑖[𝑀𝑣(𝐺)] ≥𝛾[𝑀𝑣(𝐺)].

Proof: By the definition 𝑉[𝑀𝑣(𝐺)] = 𝑉′ ∪𝐸′ ∪𝑅′. Let the dominating set of 𝑀𝑣(𝐺) be 𝐷= {𝑢𝑖 ′/ 𝑢𝑖 𝑃 ′ ∈𝑉[𝑀𝑣(𝐺)]}. In subsequent cases, we shall prove that. Case 1: Let G be a path.

By the Observation 3.3, 〈𝐷〉 is totally disconnected. Hence 𝑖[𝑀𝑣(𝑃𝑛)] = 𝛾[𝑀𝑣(𝑃𝑛)]. It follows. Case 2: Let G be a tree.

By the Theorem 4.6, 〈𝐷〉 is totally disconnected. Hence 𝑖[𝑀𝑣(𝑇)] = 𝛾[𝑀𝑣(𝑇)]. It follows. Case 3: Now we consider the cycle 𝐶𝑛.

By the Theorem 2.2 and Theorem 4.7, it follows that 𝑖[𝑀𝑣(𝐶𝑛)] ≥𝛾[𝑀𝑣(𝐶𝑛)]. Case 4: Consider 𝐺 be any graph. By Observation 3.3, Theorem 4.6, Theorem 2.2 and Theorem 4.7, it follows that 𝑖[𝑀𝑣(𝐺)] ≥ 𝛾[𝑀𝑣(𝐺)]. From the above cases, we can say that 𝑖[𝑀𝑣(𝐺)] ≥ 𝛾[𝑀𝑣(𝐺)].

Theorem 4.9: For every graph 𝐺(𝑝, 𝑞), 𝑖[𝑀𝑣(𝐺)] ≥⌈ 1+∆(𝐺)⌉. Proof From Theorem 2.3, 𝛾[𝑀𝑣(𝐺)] ≥⌈ 𝑃 1 + ∆(𝐺)⌉… … … … . (1) 𝑃 By Theorem 4.8, 𝑖[𝑀𝑣(𝐺)] ≥ 𝛾[𝑀𝑣(𝐺)] … … … … . (2) We have, From equation (1) and equation (2), 𝑖[𝑀𝑣(𝐺)] ≥⌈ 1+∆(𝐺)⌉… … … … . (3)

Conclusions

In this paper we established nonsplit domination results on vertex semi-middle graph. Many bounds on domination number of vertex semi-middle graph are obtained.

1. Harary F. Graph Theory, Addison-Wesley Reading Mass. 1969;72:107.
2. Haynes TW, Hedetniemi ST, Slater PJ. Fundamentals of Domination in Graphs, Marcel Dekker: New York, 1997.
3. Haynes TW, Hedetniemi ST, Slater PJ. Domination in Graphs: Advanced Topics, Marcel Dekker: New York, 1998.
4. Kulli VR, Janakiram B, Niranjan KM. The dominating graph. Graph Theory Notes of New York. 2004;46:5-8.
5. Kulli VR, Janakiram B, Niranjan KM. The Vertex Minimal Dominating Graph, Acta Ciencia Indica. Mathematics. 2002;28(3):435-440.
6. Kulli VR, Janakiram B. The Split Domination Number of Graph, Graph Theory Notes of New York, New York Academy of Sciences. 1997;31:16-19.
7. Kulli VR, Niranjan KM. The Semi-Splitting Block Graph of a Graph, Journal of Scientific Research. 2010;2(3):485-488.
8. Kulli VR, Basavanagouda B, Niranjan KM. Quasi-Total Graphs with Crossing Numbers, Journal of Scientific Research. 2010;2(2):257-263.
9. Kulli VR, Niranjan KM. On Minimally Nonouterplanarity of The Semi-Total (Point) Graph of a Graph, J Sci. Res. 2009;1(3):551-557.
10. Kulli VR, Niranjan KM. On Minimally Nonouterplanarity of a Semi Splitting Block Graph of a Graph, International Journal of Mathematics Trends and Technology (IJMTT). 2020;66(7).
11. Kulli VR, Niranjan KM. The Semi-Splitting Block Graphs with Crossing numbers, Asian Journal of Current Research. 2020;5(1):9-16. https://www.mathsjournal.com
12. Kulli VR, Niranjan KM. The Semi-Image Neighbourhood Graph of a Graph, Asian Journal of Mathematics and Computer Research. 2020;27(2):36-41.
13. Kulli VR, Niranjan KM. The Total Closed Neighbourhood Graphs with Crossing Number Three and Four, Journal of Analysis and Computation. 2005;1(1):47-56.
14. Maralabhavi YB, Venkanagouda Goudar M, Anupama SB. Some Domination Parameters on Jump Graph, International Journal of Pure and Applied Mathematics. 2017;113:47-55.
15. Maralabhavi YB, Anupama SB, Venkanagouda Goudar M. Domination Number of Jump Graph, International Mathematical Forum, Hikari Publishing Ltd. 2013;8:753-758.
16. Niranjan KM, Rajendra Prasad KC, Venkanagouda Goudar M, Dupadahalli Basavaraja. Forbidden Subgraphs for Planar Vertex Semi-Middle Graph, JNNCE Journal of Engineering and Management. 2022;5(2):44-47.
17. Niranjan KM, Radha Iyer R, Biradar MS, Dupadahalli Basavaraja. The Semi-Splitting Block Graphs with Crossing Numbers Three and Forbidden Subgraphs for Crossing Number One, Asian Journal of Current Research. 2020;5(1):25-32.
18. Niranjan KM. Forbidden Subgraphs for Planar and Outerplanar Interms of Blict Graphs, Journal of Analysis and Computation. 2006;2(1):19-22.
19. Niranjan KM, Nagaraja P, Lokesh V. Semi-Image Neighborhood Block Graphs with Crossing Numbers, Journal of Scientific Research. 2013;5(4):295-299.
20. Niranjan KM, Nagaraja P, Lokesh V. Semi-Image Neighborhood Block Graphs with Crossing Numbers, Journal of Scientific Research. 2013;5(4):295-299.
21. Niranjan KM. Forbidden Subgraphs for Planar and Outerplanar Interms of Blict Graphs, Journal of Analysis and Computation. 2006;2(1):19-22.
22. Niranjan KM. The Semi-Image Neighbourhood Block Graph Crossing Number and Forbidden Subgraphs, International Journal of Mathematics Trends and Technology. 2022;68(4):52-58.
23. Rajendra Prasad KC, Venkanagouda Goudar M, Niranjan KM. Pathos Vertex Semi-Middle Graph of a Tree, South East Asian J of Mathematics and Mathematical Sciences. 2020;16(1):171-176.
24. Rajendra Prasad KC, Venkanagouda Goudar M, Niranjan KM. Pathos Edge Semi-Middle Graph of a Tree, Malaya Journal of Matematik. 2020;8(4):2190-2193.
25. Rajendra Prasad KC, Niranjan KM, Venkanagouda Goudar M. Vertex Semi-Middle Graph of a Graph, Malaya Journal of Matematik. 2019;7:786-789.
26. Rajendra Prasad KC, Niranjan KM, Venkanagouda Goudar M. Vertex Semi-Middle Domination in Graphs, Jour of Adv Research in Dynamical and Control Systems. 2020;12:83-89.
27. Venkanagouda Goudar M. Pathos Vertex Semientire Graph of a Tree, International Journal of Applied Mathematical Research. 2012;1(4):666-670.
28. Venkanagouda Goudar M, Ashalatha KS, Venkatesha MH. Muddebihal, On the Geodetic Number of Line Graph, Int. J Contemp. Math. Sciences. 2012;7(46):2289-2295.
29. Venkanagouda Goudar M, Rajendra Prasad KC, Niranjan KM. Split Domination Number in Vertex Semi-Middle Graph,