Search

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]

A (k,r)-coloring of a graph G is a proper coloring with k colors such that for every vertex v with degree d(v) in G, the color number of the neighbors of v is at least min{d(v),r}. The smallest integer k such that G has a (k,r)-coloring is called the r-hued chromatic number and denoted by χr(G). In Kaliraj et al. [Taibah Univ. Sci.14 (2020) 168–171], it is determined the 2-hued chromatic numbers of Cartesian product of complete graph and star graph. In this paper, we extend its result and determine the r-hued chromatic number of Cartesian product of complete graph and star graph. [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]

• 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]

Abstract: Let be the complete graph of order . Assume that is a -decomposition of such that is connected for each . Then for any sufficiently large , We also prove that both bounds are best possible. [Copyright &y& Elsevier]

Abstract: The Szeged index is a graph invariant which is a natural generalization of Wiener index. In this note, we disprove two recent conjectures concerning with the maximum value of Szeged index of graphs, which are due to Khalifeh et al. (Europ. J. Combinatorics (2008), doi:10.1016/j.ejc.2008.09.019) and respectively, to Gutman et al. (Groat. Chem. Acta 81 (2)(2008) 263–266) and prove a conjecture on Szeged index due to Klavzar et al. ( Appl. Math. Lett. 9 (1996), 45–49), which states that the complete bipartite graph has maximum Szeged index among all connected graphs on n vertices. The last conjecture is previously proved by Dobrynin (Croat. Chem. Acta 70(3), 819-825), but our proof turns out to be much simpler and self-contained. [Copyright &y& Elsevier]

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 . 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 with at least one edge, c o l ( G ) ≤ 2 R ( G ) , with equality if and only if G is a complete graph, possibly with some additional isolated vertices. This extends a theorem of Hansen and Vukicević. [ABSTRACT FROM AUTHOR]

Let S be a set of at least two vertices in a graph G. A subtree T of G is an S -Steiner tree if S ⊆ V (T). Two S -Steiner trees T 1 and T 2 are internally disjoint (resp. edge-disjoint) if E (T 1) ∩ E (T 2) = 0̸ and V (T 1) ∩ V (T 2) = S (resp. E (T 1) ∩ E (T 2) = 0̸). Let κ G (S) (resp. λ G (S)) be the maximum number of internally disjoint (resp. edge-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 -subsets of V (G). It is well-known that the connectivity of the line graph of a graph G is closely related to the edge-connectivity of G. Chartrand et al., Li et al., and Li et al. showed that κ k (L (G)) ≥ λ k (G) for k = 2 , 3 , 4 , respectively. In [Discrete Math. 341(2018), 1945–1951.], Li et al. also proposed the following conjecture: κ k (L (G)) ≥ λ k (G) for integer k ≥ 2 and a graph G with at least k vertices. In this paper, we show that κ k (L (G)) ≥ λ k (G) − m a d (G) 2 2 for general k , where m a d (G) is the maximum average degree of a graph G. We also show that κ k (L (G)) ≥ λ k (G) − r 2 2 for any integers k and r such that k ≤ r 2 . Finally, we show that the conjecture holds for k = 5 , and the conjecture holds for the wheel graph and the complete bipartite graph K 3 , n. [ABSTRACT FROM AUTHOR]