Search

In 1985, Fink and Jacobson gave a generalization of the concepts of domination and independence in graphs. For a positive integer k, a subset S of vertices in a graph G = ( V, E) is k- dominating if every vertex of V − S is adjacent to at least k vertices in S. The subset S is k- independent if the maximum degree of the subgraph induced by the vertices of S is less or equal to k − 1. In this paper we survey results on k-domination and k-independence. [ABSTRACT FROM AUTHOR]

The total domination subdivision number $\mathrm{sd}_{\gamma _{t}}(G)$ of a graph G is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that $\mathrm{sd}_{\gamma_{t}}(G)\leq \lfloor\frac{2n}{3}\rfloor$ for any simple connected graph G of order n≥3 other than K. We also determine all simple connected graphs G with $\mathrm{sd}_{\gamma_{t}}(G)=\lfloor\frac{2n}{3}\rfloor$ . [ABSTRACT FROM AUTHOR]

A setSof vertices in a graphGis a paired-dominating set ofGif every vertex ofGis adjacent to some vertex inSand if the subgraph induced byScontains a perfect matching. The minimum cardinality of a paired-dominating set ofGis the paired-domination number ofG, denoted by ?pr(G). IfGdoes not contain a graphFas an induced subgraph, thenGis said to beF-free. In particular ifF=K1,3 orK4-e, then we say thatGis claw-free or diamond-free, respectively. LetGbe a connected cubic graph of ordern. We show that (i) ifGis (K1,3,K4-e,C4)-free, then ?pr(G)=3n/8; (ii) ifGis claw-free and diamond-free, then ?pr(G)=2n/5; (iii) ifGis claw-free, then ?pr(G)=n/2. In all three cases, the extremal graphs are characterized. [ABSTRACT FROM AUTHOR]

A graph is ( r, k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t( G) denote the toughness of graph G. In this paper, we show that if t( G)≥4, then G is (3, k)-factor-critical for every non-negative integer k such that n+ k even, k<2 t( G)−2 and k≤ n−7. [ABSTRACT FROM AUTHOR]

A graph is ( r, k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. with an r-regular spanning subgraph). We show that every τ-tough graph of order n with τ≥2 is (2, k)-factor-critical for every non-negative integer k≤min{2τ−2, n−3}, thus proving a conjecture as well as generalizing the main result of Liu and Yu in [4]. [ABSTRACT FROM AUTHOR]