Search

A given graph H is called realizable by a graph G if G [ N (v) ] ≅ H for every vertex v of G. The Trahtenbrot-Zykov problem says that which graphs are realizable? We consider a problem somewhat opposite in a more general setting. Let F be a family of graphs: to characterize all graphs G such that G - N [ v ] ∈ F for every vertex v of G. Let T m be the set of all trees of size m ≥ 0 for a fixed nonnegative integer m, P = { P t : t > 0 } and S = { K 1 , t : t ≥ 0 } . We show that for a connected graph G with its complement G ¯ being connected, G - N [ v ] ∈ T m for each v ∈ V (G) if and only if one of the following holds: G - N [ v ] ≅ K 1 , m for each v ∈ V (G) , or G - N [ v ] ≅ P m + 1 for each v ∈ V (G) . Indeed, the graphs with later two properties are characterized by the same authors very recently (Graphs G in which G - N [ v ] has a prescribed property for each vertex v, Discrete Appl. Math., In press.). In addition, we characterize all graphs G such that G - N [ v ] ∈ S for each v ∈ V (G) and all graphs G such that G - N [ v ] ∈ P for each v ∈ V (G) . This solves an open problem raised by Yu and Wu (Graphs in which G - N [ v ] is a cycle for each vertex v, Discrete Math. 344 (2021) 112519). Finally, a number of conjectures are proposed for the perspective of the problem. [ABSTRACT FROM AUTHOR]

Let G be a graph and H be a connected graph. A subset D ⊆ V (G) is called an H -isolating set of G if G − N [ D ] contains no H as a subgraph. The H -isolation number of G , denoted by ι (G , H) , is the minimum cardinality of an H -isolating set in G. For an integer k ≥ 0 , a K 1 , k + 1 -isolating set of G is simply said to be a k -isolating set of G , and ι (G , K 1 , k + 1) is abbreviated to ι k (G) , called the k -isolation number of G. Thus, ι k (G) is the minimum cardinality of a k -isolating set D such that Δ (G − N [ D ]) ≤ k. We prove that if G is a connected graph of size m , then ι k (G) ≤ m + 1 k + 3 , unless G ≅ K 1 , k + 1 , or k = 1 and G ≅ C 6 . The extremal graphs are completely characterized. Moreover, it is proved that for any graph G with s components, ι (G , H) ≤ γ (H) m (G) + s m (H) + 1 . Several conjectures are proposed in the closing, where γ (H) is the domination number of H. [ABSTRACT FROM AUTHOR]

Let fo(G) ${f}_{o}(G)$ be the maximum order of an odd induced subgraph of G $G$. In 1992, Scott proposed a conjecture that fo(G)≥nχ(G) ${f}_{o}(G)\ge \frac{n}{\chi (G)}$ for a graph G $G$ of order n $n$ without isolated vertices, where χ(G) $\chi (G)$ is the chromatic number of G $G$. In this paper, we show that the conjecture is not true for bipartite graphs, but is true for all line graphs. In addition, we also disprove a conjecture of Berman, Wang, and Wargo in 1997, which states that fo(G)≥2n4 ${f}_{o}(G)\ge 2\unicode{x0230A}\frac{n}{4}\unicode{x0230B}$ for a connected graph G $G$ of order n $n$. Scott's conjecture is open for graphs with chromatic number at least 3. [ABSTRACT FROM AUTHOR]

In this paper, we study the Wiener index of the orientation of trees and theta‐graphs. An orientation of a tree is called no‐zig‐zag if there is no subpath in which edges change the orientation twice. Knor, Škrekovski, and Tepeh conjectured that every orientation of a tree T $T$ achieving the maximum Wiener index is no‐zig‐zag. We disprove this conjecture by constructing a counterexample. Knor, Škrekovski, and Tepeh conjectured that among all orientations of the theta‐graph Θa,b,c ${{\rm{\Theta }}}_{a,b,c}$ with a≥b≥c $a\ge b\ge c$ and b>1 $b\gt 1$, the maximum Wiener index is achieved by the one in which the union of the paths between u1 ${u}_{1}$ and u2 ${u}_{2}$ forms a directed cycle of length a+b+2 $a+b+2$, where u1 ${u}_{1}$ and u2 ${u}_{2}$ are the vertex of degree 3. We confirm the validity of the conjecture. [ABSTRACT FROM AUTHOR]

Let G be a graph. A subset D ⊆ V (G) is a decycling set of G if G - D contains no cycle. A subset D ⊆ V (G) is a cycle isolating set of G if G - N [ D ] contains no cycle. The decycling number and cycle isolation number of G, denoted by ϕ (G) and ι c (G) , are the minimum cardinalities of a decycling set and a cycle isolating set of G, respectively. Dross, Montassier and Pinlou (Discrete Appl Math 214:99–107, 2016) conjectured that if G is a planar graph of size m and girth at least g, then ϕ (G) ≤ m g . So far, this conjecture remains open. Recently, the authors proposed an analogous conjecture that if G is a connected graph of size m and girth at least g that is different from C g , then ι c (G) ≤ m + 1 g + 2 , and they presented a proof for the initial case g = 3 . In this paper, we further prove that for the cases of girth at least 4, 5 and 6, this conjecture is true. The extremal graphs of results above are characterized. [ABSTRACT FROM AUTHOR]

A set D of vertices in a graph G is a cycle isolating set of G if G - N [ D ] contains no cycle. The cycle isolation number of G, denoted by ι c (G) , is the minimum cardinality of a cycle isolating set of G. In this paper, we prove that if G is a connected graph of size m that is not a C 3 , then ι c (G) ≤ m + 1 5 , and we characterize the extremal graphs. Moreover, we conjecture that if G is a connected graph of size m that is not a C g , then ι c (G) ≤ m + 1 g + 2 , where g is the girth of G. [ABSTRACT FROM AUTHOR]

The biclique B of a graph G is a maximal induced complete bipartite subgraph of G. The biclique graph K B (G) of a graph G is the graph with the bicliques of G as its vertices where two vertices of K B (G) are adjacent if and only if they have a common vertex in G. In this paper, we disprove a conjecture of Groshaus and Montero concerning Helly property of biclique graphs (Groshaus and Montero, 2021) and two conjectures of Montero concerning vertex removal in biclique graphs (Montero, 2022). In addition, we confirm a conjecture of Montero about the structural characterization of biclique graphs in the same paper. [ABSTRACT FROM AUTHOR]

The k-component domination number γ k (G) of G is the minimum cardinality of a dominating set S of G such that each connected component of G[S] has order at least k. Clearly, γ 1 (G) is the domination number of G and γ 2 (G) is the total domination number of G. Let G be a connected graph of size m with δ (G) ≥ 2 . Sanchis (J Graph Theory 25:139–152, 1997) proved that γ 1 (G) ≤ m + 2 3 and Henning (J Graph Theory 35:21–45, 2000) proved that γ 2 (G) ≤ m + 2 2 , respectively. In this paper, we show that if G ≇ C n of order n ≥ k + 1 ≥ 4 , then γ k (G) ≤ k m + 1 k + 2 , and this bound is sharp. [ABSTRACT FROM AUTHOR]

For a sequence S = (s 1 , s 2 , ... , s k) of positive integers with s 1 ≤ s 2 ≤ ⋯ ≤ s k , a packing S -coloring of a graph G is a partition of V (G) into k subsets V 1 , V 2 , ... , V k such that for each 1 ≤ i ≤ k the distance between any two distinct vertices x , y ∈ V i is at least s i + 1. Gastineau and Togni (2016) posed an open problem: is every 3-irregular subcubic graph packing (1 , 1 , 3) -colorable? We show that this is true, improving a known result of Gastineau and Togni: every 3-irregular subcubic graph is packing (1 , 1 , 2) -colorable. Kostochka and Liu (2021) proposed an open problem: is every subcubic 2-connected outerplanar graph packing (1 , 2 , 2 , 2) -colorable? We also show that this is true. [ABSTRACT FROM AUTHOR]

A path in an edge-colored graph G is called conflict-free if there is a color used on exactly one of its edges. An edge-colored graph G is said to be conflict-free connected if any two vertices are connected by a conflict-free path. The conflict-free connection number of a connected graph G, denoted by cfc(G), is defined as the smallest number of colors in order to make it conflict-free connected. Doan and Schiermeyer (Graphs Comb 37:1859–1871, 2021) conjectured that there exists an integer n 0 , if | E (G) | ≥ n - 9 2 + 11 for any connected graph G of order n ≥ n 0 with 4 bridges, then c f c (G) = 2 or G belongs to G 1 ∪ G 2 , where G 1 and G 2 are two well-defined families of graphs. We disprove the conjecture. A refined version of the above conjecture is as follows: there exists an integer n 0 , if | E (G) | ≥ n - 7 2 + 9 for any connected graph G of order n ≥ n 0 with four bridges, then c f c (G) = 2 or G belongs to G 1 ∪ G 2 . We prove that the conjecture is true if G has at least two nontrivial blocks. [ABSTRACT FROM AUTHOR]

A path in an edge-colored graph G is called conflict-free if there is a color used on exactly one of its edges. An edge-colored graph G is said to be conflict-free connected if any two vertices are connected by a conflict-free path. The conflict-free connection number of a connected graph G, denoted by cfc(G), is defined as the smallest number of colors in order to make it conflict-free connected. Doan and Schiermeyer (Graphs Comb 37:1859–1871, 2021) conjectured that there exists an integer n 0 , if | E (G) | ≥ n - 9 2 + 11 for any connected graph G of order n ≥ n 0 with 4 bridges, then c f c (G) = 2 or G belongs to G 1 ∪ G 2 , where G 1 and G 2 are two well-defined families of graphs. We disprove the conjecture. A refined version of the above conjecture is as follows: there exists an integer n 0 , if | E (G) | ≥ n - 7 2 + 9 for any connected graph G of order n ≥ n 0 with four bridges, then c f c (G) = 2 or G belongs to G 1 ∪ G 2 . We prove that the conjecture is true if G has at least two nontrivial blocks. [ABSTRACT FROM AUTHOR]

The super line graph of index r, denoted by L r (G) , is defined for any graph G with at least r edges. Its vertices are the sets of r edges of G, and two such sets are adjacent if an edge of one is adjacent to an edge of the other. In this paper, we give an explicit characterization for all graphs G with L 2 (G) being a complete graph. We present lower bounds for the clique number and chromatic number of L 2 (G) for several classes of graphs. In addition, bounds for the domination number of L 2 (G) are established in terms of the domination number of the line graph L (G) of a graph. A number of related problems on L 2 (G) are proposed for a further study. [ABSTRACT FROM AUTHOR]

The harmonic index H (G) of a graph G is ∑ u v ∈ E (G) 2 d (u) + d (v) , where d (v) is the degree of v ∈ V (G). We show that H (L (T)) > n 4 for any tree T of order n ≥ 3 , which confirm the validity of a conjecture proposed by Zhang and Wu. In addition, the same lower bound holds for a unicyclic graph G of order n. Two relevant conjectures are proposed as well. [ABSTRACT FROM AUTHOR]

The forest number f(G) of a graph G is max { | S | : S ⊆ V (G) and G[S] contains no cycle } . In this paper, we investigate the forest number of several kinds of products of two graphs G and H, such as cartesian product G □ H , direct product G × H and lexicographic product G[H]. The sharp bounds are given for Cartesian product and direct product of two graphs. However, characterizing all graphs attaining these bounds is difficult. Among other things, it is shown that (1) for any connected nontrivial graph G of order n with α (G) = 2 , and any nontrivial forest H, f (G □ H) = α (G) f (H) + 1 if and only if G ≅ K n - e and H ∈ { P 3 , P 4 } , or δ (G) = n - 2 and H ≅ K 2 . (2) f (G × K 2) = m + 1 for any graph G of order m with δ (G) ≥ m 2 + 1 . (3) For two nonempty graphs G and H, f (G [ H ]) = α (G) f (H) . In addition, a number of related conjectures are proposed. [ABSTRACT FROM AUTHOR]

For a graph G, a function f : V (G) → { 0 , 1 , 2 , … , d i a m (G) } is called a dominating broadcast on G if for each vertex u ∈ V (G) , there exists a vertex v in G with f (v) > 0 such that d G (u , v) ≤ f (v) , where d G (u , v) denotes the distance between u and v in G. The cost of a dominating broadcast f is ∑ v ∈ V (G) f (v) . The broadcast domination number of G, denoted by γ b (G) , is the minimum cost of a dominating broadcast in G. For an integer k ≥ 1 , a function f : V (G) → { 0 , 1 , 2 , … , k } is called a k-limited dominating broadcast in G if for each vertex u ∈ V (G) , there exists a vertex v in G with f (v) > 0 such that d G (u , v) ≤ f (v) . The cost of a k-limited dominating broadcast f is ∑ v ∈ V (G) f (v) . The k-limited broadcast domination number of G, denoted by γ b , k (G) , is the minimum cost of a k-limited dominating broadcast in G. Henning, MacGillivray, Yang (Discrete Appl. Math. 285 (2020) 691-706) posed a conjecture which says that G is a cubic graph on n vertices, then γ b , 2 (G) ≤ n 3 . In this paper, we show that if G is a cubic graph on n vertices, then γ b (G) ≤ n 3 , and this bound is sharp. [ABSTRACT FROM AUTHOR]

The edge weight, denoted by Δ e (G) , of a graph G is max { d G (u) + d G (v) : u v ∈ E (G) } . An edge-coloring of a graph G is injective if for any two distinct edges e 1 and e 2 , the colors of e 1 and e 2 are distinct if they are at distance 2 in G or in a common triangle. The injective chromatic index of G, denoted by χ i ′ (G) , is the minimum number of colors needed for an injective edge-coloring of G. Ferdjallah, Kerdjoudj and Raspaud (Injective edge-coloring of sparse graphs, 2019, ) posed a conjecture which says that if G is subcubic graph, then χ i ′ (G) ≤ 6 . Kostochka, Raspaud and Xu (Eur J Combin 96:103355, 2021) showed that if G is a subcubic graph, then χ i ′ (G) ≤ 7 . We extend the above result by showing that χ i ′ (G) ≤ 4 , if Δ e (G) ≤ 5 , 7 , if Δ e (G) ≤ 6 , 12 , if Δ e (G) ≤ 7. In addition, we prove that χ i ′ (G) ≤ 6 for any subcubic claw-free graph, and this bound is sharp. [ABSTRACT FROM AUTHOR]

Let G be a graph with minimum degree s , and let a and b be positive integers such that a + b ≤ s and at one of the following is true: (i) a and b are both even or (i i) G is at least (a + b − 1) -edge-connected. Then G can be decomposed into two spanning subgraphs G 1 and G 2 such that G 1 has minimum degree a and G 2 has minimum degree b. This extends two well-known results due to Petersen and Plesník, respectively: any 2 k -regular graph G has a 2-factor; a k -regular and (k − 1) -edge connected graph G with even order has a perfect matching. Note that the restriction on edge connectivity is necessary and there is a stronger result due to Kano (1985) when both a and b are even. [ABSTRACT FROM AUTHOR]

The k -component domination number γ k (G) of G is the minimum cardinality of a dominating set S of G such that each component of G [ S ] has order at least k. Clearly, γ 1 (G) is the domination number of G and γ 2 (G) is the total domination number of G. With a finite set of exceptional graphs, McCuaig and Shepherd (1989) [13] proved that γ 1 (G) ≤ 2 5 n and Henning (2000) [11] proved that γ 2 (G) ≤ 4 7 n respectively. As an extension, Alvarado et al. (2016) [1] posed a conjecture which says that if G is a connected graph of order n ≥ k + 1 and δ (G) ≥ 2 , then γ k (G) ≤ 2 k n 2 k + 3 unless G belongs to a set of exceptional graphs. In this paper, we confirm the validity of the above conjecture. Moreover, we characterize those graphs of order n which are edge-minimal with respect to satisfying G connected, δ (G) ≥ 2 and γ k (G) ≥ 2 k n 2 k + 3. This strengthens a result of Alvarado, Dantas, and Rautenbach in the same paper. [ABSTRACT FROM AUTHOR]

Let F be a family of graphs. We characterize all graphs G such that for any vertex v ∈ V (G) , G − N [ v ] is isomorphic to a member of the family F if F is one of the following four families of graphs: { K 1 , t } for any fixed nonnegative integer t ; { P l } for any fixed integer l ≥ 1 ; 1-regular graphs; all cliques. This partially solves some open problems raised by Yu and Wu. [ABSTRACT FROM AUTHOR]

In this paper, we establish sharp upper and lower bounds for the size of connected graphs with fixed order and feedback number. Corresponding extremal graphs are also characterized. As a corollary, we give a sharp lower bound for the forest number of a graph in terms of its order and size, which extends a result of Shi and Xu (2017). [ABSTRACT FROM AUTHOR]

The Randić index of a graph G, denoted by R (G) , is defined as the sum of 1 / d (u) d (v) for all edges u v of G, where d (u) denotes the degree of a vertex u in G. In this note, we show that R (L (T)) > n 4 for any tree T of order n ≥ 3 . A number of relevant conjectures are proposed. [ABSTRACT FROM AUTHOR]

For a graph G , a subset S ⊆ V (G) is called a cycle isolating set of G if G − N [ D ] contains no cycle. The cycle isolation number of G , denoted by ι c (G) , is the minimum cardinality of a cycle isolating set of G. Recently, Borg proved that if G is a connected n -vertex graph that is not a triangle, then ι c (G) ≤ n 4. In this paper, we prove that if G is a connected triangle-free n -vertex graph that is not a 4-cycle, then ι c (G) ≤ n 5. In particular, we characterize the subcubic graphs that attain the bound. For graphs with larger girth, several conjectures are proposed. [ABSTRACT FROM AUTHOR]

Let G be a graph and P be a property of graphs. A subset S ⊆ V (G) is called a P -admissible set of G if G - N [ S ] admits the property P . The P -admission number of G, denoted by η (G , P) , is the cardinality of a minimum P -admissible set in G. For a positive integer k, we say a graph G has the property R k if the radius of each component of G is at most k. In particular, η (G , R 1) is the cardinality of a smallest set S such that each component of G - N [ S ] has a universal vertex. In this paper, we establish sharp upper bound for η (G , R 1) for a connected graph G. We show that for a connected graph G ≠ C 7 of order n, η (G , R 1) ≤ n 4 . The bound is sharp. Several related problems are proposed. [ABSTRACT FROM AUTHOR]

A subset S ⊆ V (G) is called an F -isolating set of a graph G if G − N [ S ] contains no subgraph isomorphic to any F ∈ F , where F is a family of connected graphs. The F -isolation number of G , denoted by ι (G , F) , is the minimum cardinality of an F -isolating set in G. Denote ι (G , { K 1 , k + 1 }) simply by ι k (G). Thus, ι 1 (G) is the cardinality of a smallest set S such that G − N [ S ] consists of isolated vertices and isolated edges only. In this paper, we prove that if G is a connected graph of order n and different from P 3 , C 3 or C 6 , then ι 1 (G) ≤ 2 7 n. Further, if g i r t h (G) ≥ 7 , then this bound can be improved to n 4 unless G is P 3 , C 7 or C 11. Both two bounds above are sharp. Two related problems are proposed. [ABSTRACT FROM AUTHOR]

A strong edge coloring of a graph G is an assignment of colors to the edges of G such that two distinct edges are colored differently if their distance is at most two. The strong chromatic index of graph G , denoted by χ s ′ (G) , is the minimum number of colors needed for a strong edge coloring of G. A Halin graph G is a plane graph constructed from a tree T without vertices of degree two by connecting all leaves through a cycle C. In 2018, Hu et al. (2018) posed a conjecture which says that if G = T ∪ C is a Halin graph other than a wheel W n , N e 2 , or N e 4 , then χ s ′ (G) ≤ χ s ′ (T) + 2. The bound can be achieved. In this paper, we show that the above conjecture is true. This improves the known bound χ s ′ (G) ≤ χ s ′ (T) + 3 obtained by Lai et al. (2012), and extends the results on Halin graphs G with Δ (G) ≤ 3 obtained by Lih and Liu (2012) and Δ (G) ≤ 4 obtained by Hu et al. (2018), respectively. [ABSTRACT FROM AUTHOR]

In this note, we disprove two conjectures on no hole anti- n -labeling of graphs proposed by Guan et al. (2019), and characterize a graph G with λ n n h (G) = α (G) , where λ n n h (G) and α (G) denote the no hole anti- n -labeling number and the independence number of G , respectively. [ABSTRACT FROM AUTHOR]

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]

In this note, we disprove three conjectures on power domination of regular graphs, one of which is posed by Dorbec et al. (2013), two of which are posed by Lu et al. (2020), respectively. [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]

Let G be a graph and F be a family of connected graphs. A subset S of G is called an F -isolating set if G - N [ S ] contains no member in F as a subgraph, and the minimum cardinality of an F -isolating set of graph G is called the F -isolation number of graph G, denoted by ι (G , F) . For simplicity, let ι (G , { K 1 , k + 1 }) = ι k (G) . Thus, ι 1 (G) is the cardinality of a smallest set S such that G - N [ S ] consists of K 1 and K 2 only. In this paper, we prove that for any claw-free cubic graph G of order n, ι 1 (G) ≤ n 4 . The bound is sharp. [ABSTRACT FROM AUTHOR]

Abstract Very recently, Aouchiche and Hansen gave an upper bound on the ratio of G A ∕ χ of the geometric–arithmetic index G A (G) and the chromatic number χ (G) of a graph. Furthermore, they proposed several conjectures on the relation between geometric–arithmetic index and chromatic number, and clique number. In this note, we disprove four of those conjectures. In addition, we present a sufficient condition for an edge e ∈ E (G) with G A (G − e) < G A (G). [ABSTRACT FROM AUTHOR]

• Many thanks to the reviewers for their comments, the paper is carefully revised according to the reviewers' comments, mainly to correct typos. • All modifications (in red) can be easily found in text. For two graphs H and F , a spanning subgraph G of H is weakly (H , F) -saturated if there is no subgraph isomorphic to F in G , but there is an ordering of the elements in E (H) ∖ E (G) so that they can be added one at a time, and each addition of an element yields a subgraph F ′ isomorphic to F. The weak saturation number w s a t (H , F) of F with respect to H is the minimum size of a weakly (H , F) -saturated graph. For any two integers r ≥ 3 and a ≥ 1 , we give upper bounds for w s a t (K n , r K a , a) and w s a t (K n , r K a , a + 1) respectively. In addition, an upper bound of w s a t (K n , K a , b) is established for integers n , a , b satisfying a + 1 < b < 3 a − 2 , a ≥ 3 and n ≥ 2 (a + b − 2). Thereby, we are able to answer a question of Kronenberg et al. (Weak saturation numbers of complete bipartite graphs in the clique, J. Combin. Theory Ser. A 178 (2021) 105357) concerning w s a t (K n , K a , a + 2) in the negative. [ABSTRACT FROM AUTHOR]

A path in a vertex-colored graph is called conflict-free if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be conflict-free vertex-connected if any two vertices of the graph are connected by a conflict-free path. The conflict-free vertex-connection number, denoted by v c f c (G) , is defined as the smallest number of colors required to make G conflict-free vertex-connected. Li et al. [Conflict-free vertex-connections of graphs, preprint (2017), arXiv:1705.07270v1[math.CO]] conjectured that for a connected graph G of order n , v c f c (G) ≤ v c f c (P n). We confirm that the conjecture is true and poses two relevant conjectures. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a graph of order n , and λ = ( λ 1 , λ 2 , … , λ p ) a sequence of positive integers. The sequence λ is admissible for G if λ 1 + ⋯ + λ p = n . Such an admissible sequence λ is said to be realizable in G if there exists a partition ( V 1 , V 2 , … , V p ) of the vertex set V such that V i induces a connected subgraph of order n i in G for each i . If every admissible sequence is realizable in G , then we say that G is arbitrarily partitionable (AP, for short). We show that if a tree T of maximum degree at most n + 1 has a path containing all the vertices of degree n + 1 , then T □ C n has a Hamiltonian path. In particular, for any caterpillar T with maximum degree at most n + 1 , T □ C n is AP. In addition, if T is a caterpillar with Δ ( T ) ≥ n + 4 , then T □ C n is not AP. For the cases n + 2 ≤ Δ ( T ) ≤ n + 3 , we present some sufficient conditions for a caterpillar T such that T □ C n is AP. [ABSTRACT FROM AUTHOR]

Let S be a set of at least two vertices in a graph G . A subtree T of G is a S -Steiner tree if S ⊆ V ( T ) . Two S -Steiner trees T 1 and T 2 are edge-disjoint (resp. internally vertex-disjoint ) if E ( T 1 ) ∩ E ( T 2 ) = ∅ (resp. E ( T 1 ) ∩ E ( T 2 ) = ∅ and V ( T 1 ) ∩ V ( T 2 ) = S ). Let λ G ( S ) (resp. κ G ( S ) ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) S -Steiner trees in G , and let λ k ( G ) (resp. κ k ( G ) ) be the minimum λ G ( S ) (resp. κ G ( S ) ) for S ranges over all k -subset of V ( G ) . Kriesell conjectured that if λ G ( { x , y } ) ≥ 2 k for any x , y ∈ S , then λ G ( S ) ≥ k . He proved that the conjecture holds for | S | = 3 , 4 . In this paper, we give a short proof of Kriesell’s Conjecture for | S | = 3 , 4 , and also show that λ k ( G ) ≥ 1 k − 1 k ℓ 2 (resp. κ k ( G ) ≥ 1 k − 1 k ℓ 2 ) if λ ( G ) ≥ ℓ (resp. κ ( G ) ≥ ℓ ) in G , where k = 3 , 4 . Moreover, we also study the relation between κ k ( L ( G ) ) and λ k ( G ) , where L ( G ) is the line graph of G . [ABSTRACT FROM AUTHOR]

A strong edge coloring of a graph G is an assignment of colors to the edges of G such that two distinct edges are colored differently if they are adjacent to a common edge or share an endpoint. The strong chromatic index of a graph G , denoted by χ s ′ ( G ) , is the minimum number of colors needed for a strong edge coloring of G . We determine the strong chromatic index of the generalized Petersen graphs P ( n, k ) when 1 ≤  k  ≤ 3. [ABSTRACT FROM AUTHOR]

A P 3 ⃗ -decomposition of a directed graph D is a partition of the arcs of D into directed paths of length 2. In this paper, we give a characterization for a tournament and a bipartite digraph admitting a P 3 ⃗ -decomposition. This solves a problem posed by Diwan (2016). [ABSTRACT FROM AUTHOR]

Dvořák et al. introduced a variant of the Randić index of a graph G , denoted by R ′ ( G ) , where R ′ ( G ) = ∑ u v ∈ E ( G ) 1 max { d ( u ) , d ( v ) } , and d ( u ) denotes the degree of a vertex u in G . The coloring number c o l ( G ) of a graph G is the smallest number k for which there exists a linear ordering of the vertices of G such that each vertex is preceded by fewer than k of its neighbors. It is well-known that χ ( G ) ≤ c o l ( G ) for any graph G , where χ ( G ) denotes the chromatic number of G . In this note, we show that for any graph G without isolated vertices, c o l ( G ) ≤ 2 R ′ ( G ) , with equality if and only if G is obtained from identifying the center of a star with a vertex of a complete graph. This extends some known results. In addition, we present some new spectral bounds for the coloring and achromatic numbers of a graph. [ABSTRACT FROM AUTHOR]

For an integer k ≥ 2 , a vertex partition (V 1 , ... , V s) of a graph G is called a k -good partition if d G [ V i ] (v) ≡ 1 (mod k) for each v ∈ V i , i ∈ { 1 , ... , s }. We characterize all trees with a k -good partition. Let f 1 , k (G) = max { | V (H) | : H is an induced subgraph H of G with d H (v) ≡ 1 (mod k) for every vertex v }. In 1997, Berman et al. (1997) showed that f 1 , k (T) ≥ 2 ⌊ n + 2 k − 3 2 k − 1 ⌋ for any tree T of order n. By sacrificing the bound slightly, but with a much simpler way, we are able to show that f 1 , k (T) ≥ n k , with equality if and only if T is the balanced double star of order 2 k. Let f 0 , k 1 (T) be the maximum cardinality of a subset S ⊆ V (T) with d T [ S ] (v) = 1 or d T [ S ] (v) ≡ 0 (mod k) for each v ∈ S. In addition, we give a short proof of the result, due to Huang and Hou [9], that f 0 , k 1 (T) ≥ 2 n 3 for any tree T and integer k ≥ 3. [ABSTRACT FROM AUTHOR]

Amos et al. (2015) introduced the notion of the k -forcing number of graph for a positive integer k as the generalization of the zero forcing number of a graph. The k -forcing number of a simple graph G , denoted by F k ( G ) , is the minimum number of vertices that need to be initially colored so that all vertices eventually become colored during the discrete dynamical process defined by the following rule. Starting from an initial set of colored vertices and stopping when all vertices are colored: if a colored vertex has at most k non-colored neighbors, then each of its non-colored neighbors become colored. Particularly, with a close connection to the maximum nullity of a graph, F 1 ( G ) is widely studied under the name of the zero forcing number, denoted by Z ( G ) . Among other things, Amos et al. proved that for a connected graph G of order n with Δ = Δ ( G ) ≥ 2 , Z ( G ) ≤ ( Δ − 2 ) n + 2 Δ − 1 , and this inequality is sharp. Moreover, they conjectured that Z ( G ) = ( Δ − 2 ) n + 2 Δ − 1 if and only if G = C n , G = K Δ + 1 or G = K Δ , Δ . In this note, we show the above conjecture is true. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a simple graph with vertex set V ( G ) = { v 1 , v 2 , … , v n } and edge set E ( G ) . Let D ( G ) be the distance matrix of G . For a given nonnegative integer k , when n is sufficiently large with respect to k , we show that λ n − k ( D ) ≤ − 1 , thereby solving a problem proposed by Lin et al. (2014) [8] . The distance Laplacian spectral radius of a connected graph G is the spectral radius of the distance Laplacian matrix of G , defined as D L ( G ) = Tr ( G ) − D ( G ) , where Tr ( G ) is the diagonal matrix of vertex transmissions of G . Aouchiche and Hansen (2014) [3] conjectured that m ( λ 1 ( D L ) ) ≤ n − 2 when G ≇ K n , and the equality holds if and only if either G ≅ K 1 , n − 1 or G ≅ K n 2 , n 2 . In this paper, we confirm the conjecture. [ABSTRACT FROM AUTHOR]

The Catalan-Larcombe-French sequence $\{P_{n}\}_{n\geq0}$ arises in a series expansion of the complete elliptic integral of the first kind. It has been proved that the sequence is log-balanced. In the paper, by exploring a criterion due to Chen and Xia for testing 2-log-convexity of a sequence satisfying three-term recurrence relation, we prove that the new sequence $\{P^{2}_{n}-P_{n-1}P_{n+1}\}_{n\geq1}$ are strictly log-convex and hence the Catalan-Larcombe-French sequence is strictly 2-log-convex. [ABSTRACT FROM AUTHOR]

• We disprove a conjecture proposed by Fiedorowicz, Sidorowicz, Sopena (Appl. Math. Comput. 410 (2021) 126253). • In addition, we find a result of the above paper is not correct. • Two sufficient conditions are given for a hamiltonian digraph D with w c → (D) = 2. Under an arc-coloring c of a digraph D , if for each pair of vertices (u , v) , there exists a directed walk from u to v satisfying that any two consecutive arcs of it have different colors, we say that D is properly-walk connected, and c is a proper-walk coloring of D. The proper-walk connection number w c → (D) of D is the least integer k such that D has a proper-walk coloring with k colors. Fiedorowicz, Sidorowicz, Sopena (Appl. Math. Comput. 410 (2021) 126253) conjectured that if D is a hamiltonian digraph with δ (D) ≥ 2 , then w c → (D) ≤ 2. In this paper, we disprove the conjecture by constructing two families of counterexamples. Also, we present some cases for a hamiltonian digraph D having w c → (D) = 2. In addition, we find that Observation 15 is not true in the same paper. [ABSTRACT FROM AUTHOR]

It is well known that a graph is outerplanar if and only if it is K 4 -minor free and K 2 , 3 -minor free. Campos and Wakabayashi (2013) recently proved that γ ( G ) ≤ ⌊ n + k 4 ⌋ for any maximal outerplanar graph G of order n ≥ 3 with k vertices of degree 2, where γ ( G ) denotes the domination number of G . Tokunaga (2013) provided a short proof for the above theorem. Based on some structural properties of K 2 , 3 -minor free graphs and K 4 -minor free graphs, applying the idea of Tokunaga we extend the theorem of Campos and Wakabayashi to all maximal K 4 -minor free graphs and all maximal K 2 , 3 -minor free graphs. We also disprove two conjectures of Tokunaga on planar graphs. [ABSTRACT FROM AUTHOR]

The vertex arboricity $$\rho (G)$$ of a graph $$G$$ is the minimum number of colors to color $$G$$ such that each color class induces a forest. The list vertex arboricity $$\rho _l(G)$$ is the list-coloring version of this concept. Zhen and Wu conjectured that $$\rho _l(G)=\rho (G)$$ whenever $$|V(G)|\le 3\rho (G)$$ . In this paper, we prove the weaker version of the conjecture obtained by replacing $$3\rho (G)$$ with $$\frac{5}{2}\rho (G)+\frac{1}{2}$$ . [ABSTRACT FROM AUTHOR]

A clique of a graph G is a complete subgraph maximal under inclusion and having at least two vertices. A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G . The clique-transversal number, denoted by τ c ( G ) , is the cardinality of a minimum clique-transversal set in G . Wang et al. (2014) proved that τ c ( G ) = ⌈ n 3 ⌉ for any 2-connected { K 1 , 3 , K 4 } -free 4-regular graph of order n , and conjectured that τ c ( G ) ≤ 10 n + 3 27 for a connected { K 1 , 3 , K 4 } -free 4-regular graph of order n . In this paper, we give a short proof of the aforementioned theorem of Wang et al. and show that the above conjecture is true, apart from only three exceptions. [ABSTRACT FROM AUTHOR]