ON THE MONOPOLY OF GRAPHS
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
For a graph G(V,E), a subset D of vertices of G is called a monopoly set of G if for every vertex v ∈ V - D has at least d(v) / 2 neighbors in D. The monopoly size of G is the smallest cardinality of a monopoly set in G, denoted by mo(G). In this paper, we investigate the relationship between monopoly size of graphs and some other parameters of a graph namely domination number (G) and k-dominating number k(G). Bounds on monopoly size of graphs in terms maximum degree, minimum degree, diameter, algebraic connectivity and Laplacian spectral radius of a graph are found.
Abstract
For a graph G(V,E), a subset D of vertices of G is called a monopoly set of G if for every vertex v ∈ V - D has at least d(v) / 2 neighbors in D. The monopoly size of G is the smallest cardinality of a monopoly set in G, denoted by mo(G). In this paper, we investigate the relationship between monopoly size of graphs and some other parameters of a graph namely domination number (G) and k-dominating number k(G). Bounds on monopoly size of graphs in terms maximum degree, minimum degree, diameter, algebraic connectivity and Laplacian spectral radius of a graph are found.
참고문헌 (15)
- J. Bermond, "The power of small coalitions in graphs", Discrete Applied Mathematics, 127, pp.399~414 (2003)
- J. E. Dunbar, "α-domination", Discrete Mathematics, 211, pp.11~26 (2000)
- O. Favaron, "Offensive alliances in graphs", Discussiones Mathematicae Graph Theory, 24, pp.263~275 (2002)
- H. Fernau, "Offensive r-alliances in graphs", Discrete Applied Mathematics, 157, pp.177~182 (2009)
- H. Fernau, "A survey alliances related parameters in graph", Electronic Journal of Graph Theory and Applications, 2, pp.70~86 (2014)
- M. Fiedler, "A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory", Czechoslovak Mathematical Journal, 25, pp.619~633 (1975)
- P. Flocchini, "On time versus size for monotone dynamic monopolies in regular topologies", Journal of Discrete Algorithms, 1, pp.129~150 (2003)
- F. Harary, "Graph Theory" (1969), Addison Wesley
- T. W. Haynes, "Fundamentals of Domination in Graphs" (1998), Marcel Dekker,Inc.
- K. Khoshkhak, "A study of monopoly in graphs", Graph and Combinatorial Mathematics, 29, pp.1417~1427 (2013)
- V.R. Kulli, "Theory of Domination in Graphs" (2010), Vishwa International Publications
- R. Merris, "Laplacian matrices of graphs: A survey, Linear Algebra and its Applications", pp.143~176 (1994), Elsevier Science Inc
- A. Mishra, "Minimum monopoly in regular and tree graphs", Discrete Mathematics, 306(14), pp.1586~1594 (2006)
- D. Peleg, "Local majorities; coalitions and monopolies in graphs; a review", Theoretical Com-puter Science, 282, pp.231~257 (2002)
- M. Zaker, "On dynamic monopolies of graphs with general thresholds", Discrete Mathematics, 312, pp.1136~1143 (2012)