Search

A graph G of order n is said to be k -factor-critical for integers 1 ≤ k < n , if the removal of any k vertices results in a graph with a perfect matching. A k -factor-critical graph G is called minimal if for any edge e ∈ E (G) , G − e is not k -factor-critical. In 1998, O. Favaron and M. Shi conjectured that every minimal k -factor-critical graph of order n has minimum degree k + 1 and confirmed it for k = 1 , n − 2 , n − 4 and n − 6. By using a novel approach, we have confirmed it for k = n − 8 in a previous paper. Continuing with this method, we confirm the conjecture when k = n − 10 in this paper. [ABSTRACT FROM AUTHOR]

Let k be a positive integer and let G = (V (G) , E (G)) be a graph. A vertex set D is a k -component dominating set of G if every vertex outside D in G has a neighbor in D and every component of the subgraph G [ D ] of G induced by D contains at least k vertices. The minimum cardinality of a k -component dominating set of G is the k -component domination number γ k (G) of G. It was conjectured that if G is a connected graph of order n ≥ k + 1 , and minimum degree at least 2, then γ k (G) ≤ 2 k n 2 k + 3 except for a finite set of graphs. In this paper, we focus on the parameter γ 3 (G) of G. We first determine the exact values of 3-component domination numbers of paths and cycles. We then proceed to show that if G is a connected graph of order n with minimum degree at least 2 and maximum degree at most 3, then γ 3 (G) ≤ 2 n 3 , unless G is one of seven special graphs. This result provides positive support for the conjecture and also generalizes a result by Alvarado et al. (2016) [1]. [ABSTRACT FROM AUTHOR]

Let k ≥ 2 be an integer. We say that a graph G is (K 2 ∪ k K 1) -free if it does not contain K 2 ∪ k K 1 as an induced subgraph. Recently, Shi and Shan conjectured that every 1-tough and 2 k -connected (K 2 ∪ k K 1) -free graph is hamiltonian. In this paper, we solve this conjecture by proving that every 1-tough and k -connected (K 2 ∪ k K 1) -free graph with minimum degree at least 3 (k − 1) 2 is hamiltonian or the Petersen graph. [ABSTRACT FROM AUTHOR]