TAILIEUCHUNG - Báo cáo khoa học:Global defensive alliances in graphs

A defensive alliance in a graph G = (V,E) is a set of vertices S V satisfying the condition that for every vertex v 2 S, the number of neighbors v has in S plus one (counting v) is at least as large as the number of neighbors it has in V − S. Because of such an alliance, the vertices in S, agreeing to mutually support each other, have the strength of numbers to be able to defend themselves from the vertices in V − S. A defensive alliance S is called global if it effects every vertex in V − S, that is,. | Global defensive alliances in graphs 1Teresa W. Haynes 2Stephen T. Hedetniemi 3Michael A. Henning department of Mathematics East Tennessee State University Johnson City TN 37614-0002 USA email haynes@ department of Computer Science Clemson University Clemson SC 29634 USA email hedet@ 3School of Mathematics Statistics Information Technology University of KwaZulu-Natal Pietermaritzburg 3209 South Africa email henning@ Submitted Jan 18 2002 Accepted Nov 26 2003 Published Dec 8 2003 MR Subject Classifications 05C69 05C05 Abstract A defensive alliance in a graph G V E is a set of vertices S c V satisfying the condition that for every vertex v E S the number of neighbors v has in S plus one counting v is at least as large as the number of neighbors it has in V S. Because of such an alliance the vertices in S agreeing to mutually support each other have the strength of numbers to be able to defend themselves from the vertices in V S. A defensive alliance S is called global if it effects every vertex in V S that is every vertex in V S is adjacent to at least one member of the alliance S . Note that a global defensive alliance is a dominating set. We study global defensive alliances in graphs. Research supported in part by the South African National Research Foundation and the University of Natal. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R47 1 1 Introduction Alliances in graphs were first defined and studied by Hedetniemi Hedetniemi and Kristiansen in 4 . In this paper we initiate the study of global defensive alliances listed as an open problem in 4 but first we give some terminology and definitions. Let G V E be a graph with IVI n and IEI m. An endvertex is a vertex which is only adjacent to one vertex. An endvertex in a tree T is also called a leaf while a support vertex of T is a vertex adjacent to a leaf. For a nonempty subset S Q V we denote the subgraph of G induced by S by S . For any vertex v E V the open neighborhood of v

• Báo cáo khoa học
• Global defensive alliances i
• mathematical knowledge
• reports of mathematics
• mathematical works
• Even circuits
• defensive alliance