<p>A set <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(D \subseteq V\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>D</mi> <mo>⊆</mo> <mi>V</mi> </mrow> </math></EquationSource> </InlineEquation> of a graph <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(G =(V, E)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is called a <i>dominating set</i> of <i>G</i> if every vertex in <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(V\setminus D\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo> <mi>D</mi> </mrow> </math></EquationSource> </InlineEquation> is adjacent to at least one vertex in <i>D</i>. A dominating set <i>D</i> of a graph <i>G</i> is <i>convex dominating set</i> if all vertices from <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(u-v\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>u</mi> <mo>-</mo> <mi>v</mi> </mrow> </math></EquationSource> </InlineEquation> geodesic belong to <i>D</i> for every two vertices <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(u,v \in D\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo>∈</mo> <mi>D</mi> </mrow> </math></EquationSource> </InlineEquation>. A convex dominating set <i>D</i> of a graph <i>G</i> is <i>nonsplit convex dominating set</i> if the induced subgraph <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(G[V \setminus D]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo stretchy="false">[</mo> <mi>V</mi> <mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo> <mi>D</mi> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation> is connected. The <i>nonsplit convex domination number</i> of <i>G</i> is the minimum cardinality of a nonsplit convex dominating set <i>D</i> and it is denoted by <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\gamma _{nscon}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>γ</mi> <mrow> <mi mathvariant="italic">nscon</mi> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we initiate the study on this parameter. We establish bounds for <i>nonsplit convex domination number</i>, <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\gamma _{nscon}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>γ</mi> <mrow> <mi mathvariant="italic">nscon</mi> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, of standard graph structures. Further, we also present conditions for identifying or constructing a nonsplit convex dominating set in any connected graph <i>G</i>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Convex and Nonsplit Convex Domination in Graphs

  • Rajshree Dahal,
  • Hari Baskar Ranganathan

摘要

A set \(D \subseteq V\) D V of a graph \(G =(V, E)\) G = ( V , E ) is called a dominating set of G if every vertex in \(V\setminus D\) V \ D is adjacent to at least one vertex in D. A dominating set D of a graph G is convex dominating set if all vertices from \(u-v\) u - v geodesic belong to D for every two vertices \(u,v \in D\) u , v D . A convex dominating set D of a graph G is nonsplit convex dominating set if the induced subgraph \(G[V \setminus D]\) G [ V \ D ] is connected. The nonsplit convex domination number of G is the minimum cardinality of a nonsplit convex dominating set D and it is denoted by \(\gamma _{nscon}(G)\) γ nscon ( G ) . In this paper, we initiate the study on this parameter. We establish bounds for nonsplit convex domination number, \(\gamma _{nscon}(G)\) γ nscon ( G ) , of standard graph structures. Further, we also present conditions for identifying or constructing a nonsplit convex dominating set in any connected graph G.