We give necessary and sufficient conditions for the existence of a decomposition of the complete graph into stars which admits either a cyclic or a rotational automorphism.

For a graph G = (V, E), a set S ⊆ V is total irredundant if for every vertex v ∈ V, the set N[v] - N[S - {v}] is not empty. The total irredundance number irt(G) is the minimum cardinality of a maximal total irredundant set of G. We study the structure of the class of graphs which do not have any total irredundant sets; these are called irt(0)-graphs. Particular attention is given to the subclass of irt(0)-graphs whose total irredundance number either does not change (stable) or always changes (unstable) under arbitrary single edge additions. Also studied are irt(0)-graphs which are either stable or unstable under arbitrary single edge deletions.

For a graph G = (V, E) with order n, we define the the generalized maximum degree Δk(G) as follows: Δk(G) = max{\N (S)\ : S is a set of k vertices} for 1 ≤ k ≤ n. We give bounds on Δk(G) and characterize the trees which achieve one of these lower bounds. We define and study (k, r)-regular graphs, that is, graphs for which every subset of V with cardinality k has degree r. In particular, we show that if G is (2, r)-regular for r ≥ 3 and has sufficiently large or sufficiently small order, then G is the complete graph Kr. Finally, we characterize the regular (2, r)-regular graphs.

Let P1 and P2 be properties of vertex subsets of a graph G, and assume that every subset of V (G) with property P2 also has property P1. Let μ1(G) and μ2(G), respectively, denote the maximum cardinalities of sets with properties P1 and P2, respectively. Then μ1(G) ≥ μ2(G). If μ1(G) = μ2(G) and every μ1(G)-set is also a μ2(G)-set, then we say μ1(G) strongly equals μ2(G), written μ1(G) ≡ μ2(G). We provide a constructive characterization of the trees T such that Γ(T) ≡ β(T), where β(T) and Γ(T) are the independence and upper domination numbers of T, respectively.

Let G be a spanning subgraph of Ks,s and let H be the complement of G relative to Ks,s; that is, Ks,s = G ⊕ H is a factorization of Ks,s. For a graphical parameter μ(G), a graph G is μ(G)-critical if μ(G + e) < μ(G) for every e in the ordinary complement Ḡ of G, while G is μ(G)-critical relative to Ks,s if μ(G + e) < μ(G) for all e ∈ E(H) We show that no tree T is μ(T)-critical and characterize the trees T that are μ(T)-critical relative to Ks,s, where μ(T) is the domination number and the total domination number of T.

In this paper, we show that the domination number D of a random graph enjoys as sharp a concentration as does its chromatic number χ. We first prove this fact for the sequence of graphs {G(n, pn} n → ∞, where a two point concentration is obtained with high probability for pn = p (fixed) or for a sequence pn that approaches zero sufficiently slowly. We then consider the infinite graph G(ℤ+, p), where p is fixed, and prove a three point concentration for the domination number with probability one. The main results are proved using the second moment method together with the Borel Cantelli lemma.

No description available.

For a polynomial pz of degree n, it follows from the maximum modulus theorem that maxz=R≥1pz≤Rnmaxz=1pz. It was shown by Ankeny and Rivlin that if pz≠0 for z<1, then maxz=R≥1pz≤Rn+1/2maxz=1pz. In 1998, Govil and Mohapatra extended the above two inequalities to rational functions, and in this paper, we study the refinements of these results of Govil and Mohapatra.

This glossary contains the most common terms and parameters of graphs that appear in this book. We include these in this introductory chapter so that they need not be redefined over and over again in each subsequent chapter.

Alliances in graphs were defined to model real-life applications, where an agreement exists between two or more parties to work together for the common good. In this chapter, we explore alliances and related domination parameters.