Search

Let G be a graph and k ≥ 1 be an integer. A subset S of vertices in a graph G is called a k -component independent set of G if each component of G S has order at most k. The k -component independence number, denoted by α c k G , is the maximum order of a vertex subset that induces a subgraph with maximum component order at most k. We prove that if a tree T is of order n , then α k T ≥ k / k + 1 n. The bound is sharp. In addition, we give a linear-time algorithm for finding a maximum k -component independent set of a tree. [ABSTRACT FROM AUTHOR]

A block of a graph is a nonseparable maximal subgraph of the graph. We denote by b G the number of block of a graph G. We show that, for a connected graph G of order n with minimum degree k ≥ 1 , b G < 2 k − 3 / k 2 − k − 1 n. The bound is asymptotically tight. In addition, for a connected cubic graph G of order n ≥ 14 , b G ≤ n / 2 − 2. The bound is tight. [ABSTRACT FROM AUTHOR]

A block of a graph is a nonseparable maximal subgraph of the graph. We denote by b G the number of block of a graph G. We show that, for a connected graph G of order n with minimum degree k ≥ 1 , b G < 2 k − 3 / k 2 − k − 1 n. The bound is asymptotically tight. In addition, for a connected cubic graph G of order n ≥ 14 , b G ≤ n / 2 − 2. The bound is tight. [ABSTRACT FROM AUTHOR]

For a digraph D , the feedback vertex number τ D , (resp. the feedback arc number τ ′ D ) is the minimum number of vertices, (resp. arcs) whose removal leaves the resultant digraph free of directed cycles. In this note, we determine τ D and τ ′ D for the Cartesian product of directed cycles D = C n 1 → □ C n 2 → □ ... C n k → . Actually, it is shown that τ ′ D = n 1 n 2 ... n k ∑ i = 1 k 1 / n i , and if n k ≥ ... ≥ n 1 ≥ 3 then τ D = n 2 ... n k . [ABSTRACT FROM AUTHOR]

Jarnicki, Myrvold, Saltzman, and Wagon conjectured that if G is Hamilton-connected and not K 2 , then its Mycielski graph μ G is Hamilton-connected. In this paper, we confirm that the conjecture is true for three families of graphs: the graphs G with δ G > V G / 2 , generalized Petersen graphs G P n , 2 and G P n , 3 , and the cubes G 3 . In addition, if G is pancyclic, then μ G is pancyclic. [ABSTRACT FROM AUTHOR]