V-super vertex out-magic total labelings of digraphs
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Let $ D $ be a directed graph with $ p $ vertices and $ q $ arcs. A vertex out-magic total labeling is a bijection $ f $ from $ V(D) \cup A(D)\longrightarrow\{1, 2, \ldots$, $p+q\} $ with the property that for every $ v\in V(D)$, $f(v)+ \sum_{u\in O(v)}f((v,u))=k$, for some constant $ k $. Such a labeling is called a $ V $-super vertex out- magic total labeling ($ V $-SVOMT labeling) if $ f(V(D))=\{1, 2, 3, \ldots, p\} $. A digraph $ D $ is called a $ V $-super vertex out-magic total digraph ($ V $-SVOMT digraph) if $ D $ admits a $ V $-SVOMT labeling. In this paper, we provide a method to find the most vital nodes in a network by introducing the above labeling and we study the basic properties of such labelings for digraphs. In particular, we completely solve the problem of finding $ V $-SVOMT labeling of generalized de Bruijn digraphs which are used in the interconnection network topologies.
Abstract
Let $ D $ be a directed graph with $ p $ vertices and $ q $ arcs. A vertex out-magic total labeling is a bijection $ f $ from $ V(D) \cup A(D)\longrightarrow\{1, 2, \ldots$, $p+q\} $ with the property that for every $ v\in V(D)$, $f(v)+ \sum_{u\in O(v)}f((v,u))=k$, for some constant $ k $. Such a labeling is called a $ V $-super vertex out- magic total labeling ($ V $-SVOMT labeling) if $ f(V(D))=\{1, 2, 3, \ldots, p\} $. A digraph $ D $ is called a $ V $-super vertex out-magic total digraph ($ V $-SVOMT digraph) if $ D $ admits a $ V $-SVOMT labeling. In this paper, we provide a method to find the most vital nodes in a network by introducing the above labeling and we study the basic properties of such labelings for digraphs. In particular, we completely solve the problem of finding $ V $-SVOMT labeling of generalized de Bruijn digraphs which are used in the interconnection network topologies.
참고문헌 (17)
- J. C. Bermond, "Hypercube and Distributed Computers", pp.279~293 (1989), North-Holland
- G. S. Bloom, "On graceful directed graphs and a problem in a network addrressing", Congr. Numer, 35, pp.91~103 (1982)
- G. S. Bloom, "On graceful directed graphs", SIAM J. Algebraic Discrete Methods, 6(3), pp.519~536 (1985)
- G. S. Bloom, "Graph theory with applications to algorithms and computer science", pp.89~102 (1985), Wiley
- G. S. Bloom, "Magic digraphs", J. Combin. Math. Combin. Comput, 65, pp.205~212 (2008)
- J. A. Bondy, "Graph Theory with Applications" (1986), Elsevier, North Holland
- H. Chang, "Finding the n Most Vital Nodes in a Flow Network", Master, pp.1972
- H. Enomoto, "Super edge-magic graphs", SUT J. Math, 2(2), pp.105~109 (1998)
- J. A. Gallian, "A dynamic survey of graph labeling", Electron. J. Combin, 16 (2014)
- M. Imase, "Design to minimize diameter on building-block networks", IEEE Trans. Comput, 30(6), pp.439~442 (1981)
- M. Imase, "A design for directed graphs with minimum diameter", IEEE Trans. Comput, C-32, pp.782~784 (1983)
- J. A. MacDougall, "Vertex magic total labelings of graphs", Util. Math, 61, pp.3~21 (2002)
- J. A. MacDougall, "Super vertex magic total labelings of graphs", Proc. of the 15th Australian workshop on combinatorial algorithms, pp.222~229 (2004)
- G. Marimuthu, "E-super vertex magic labelings of graphs", Discrete Appl. Math, 160(12), pp.1766~1774 (2012)
- J. Sedlˇacek, "Problem 27, In Theory of Graphs and its Applications", Proc. Symposium, pp.163~167 (1963)
- V. Swaminathan, "Super vertex magic labeling", Indian J. Pure Appl. Math, 34(6), pp.935~939 (2003)
- T.-M. Wang, "Note on E-super vertex magic graphs", Discrete Appl. Math, 178, pp.160~162 (2014)