Uniform Length Dominating Sequence Graphs
- PDF / 252,236 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 26 Downloads / 179 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Uniform Length Dominating Sequence Graphs Aysel Erey1 Received: 29 October 2019 / Revised: 15 May 2020 Springer Japan KK, part of Springer Nature 2020
Abstract A sequence of vertices ðv1 ; . . .; vk Þ of a graph G is called a dominating closed neighborhood sequence if fv1 ; . . .; vk g is a dominating set of G and N½vi * [i1 j¼1 N½vj for every i. A graph G is said to be kuniform if all dominating closed neighborhood sequences in the graph have equal length k. Bresˇar et al. (Discrete Math 336:22–36, 2014) characterized k-uniform graphs with k 3. In this article we extend their work by giving a complete characterization of all k-uniform graphs with k 4. Keywords Domination Closed neighborhood sequence Mathematics Subject Classification 05C69
1 Introduction All graphs considered in this article are finite, simple, loopless and undirected. Given a graph G, let G be the complement of G, and let V(G) and E(G) be the vertex set and the edge set of G, respectively. A vertex u is a neighbor of vertex v if they are adjacent. The open neighborhood of v, NG ðvÞ, consists of all neighbors of v in G, and the closed neighborhood of v, NG ½v, is equal to NG ðvÞ [ fvg. We simply write N(v) and N[v] for NG ðvÞ and NG ½v, respectively when the graph G is clear from the context. A vertex v of G is called an isolated vertex of G if NðvÞ ¼ ; and it is called a dominating vertex of G if N½v ¼ VðGÞ. Two distinct vertices u and v are called true twins if N½u ¼ N½v and they are called false twins if NðuÞ ¼ NðvÞ. For a subset S of vertices of G, let NðSÞ ¼ [v2S NðvÞ and let G n S denote the subgraph induced by the vertices of VðGÞ n S (if S ¼ fug is a singleton, we simply write G n u). Also, S is called a dominating set of G if S [ NðSÞ ¼ VðGÞ, that is, every vertex in VðGÞ n S is adjacent to some vertex in S. A total dominating set of a graph G is a & Aysel Erey [email protected] 1
Department of Mathematics, Gebze Technical University, Kocaeli, Turkey
123
Graphs and Combinatorics
subset of vertices S such that NðSÞ ¼ VðGÞ, that is, every vertex in V(G) is adjacent to some vertex in S. Note that every total dominating set of a graph G is also a dominating set of G. The join of two graphs G and H, denoted by G _ H, has vertex set VðG _ HÞ ¼ VðGÞ [ VðHÞ and edge set EðG _ HÞ ¼ EðGÞ [ EðHÞ [ fuv j u 2 VðGÞ and v 2 VðHÞg. Let _t H denote the join of t copies of the graph H and tH denote disjoint union of t copies of H. The complete graph, path graph and cycle graph on n vertices are denoted by Kn ; Pn and Cn , respectively. Lastly, let Kp1 ;p2 denote the complete bipartite graph with partition sizes p1 and p2 , and let Kp1 ;...;pt denote the complete multipartite graph with t parts of sizes p1 ; . . .; pt where t 2. A sequence of k distinct vertices ðv1 ; . . .; vk Þ in G is said to have length k and it is called a dominating sequence (respectively total dominating sequence) of G if the corresponding set fv1 ; . . .; vk g is a dominating set (respectively
Data Loading...
