Internally disjoint trees in the line graph and total graph of the complete bipartite graph

Shu-Li Zhao, Rong-Xia Hao and Chao Wei

Applied Mathematics and Computation, 2022, vol. 422, issue C

Abstract: Let G be a connected graph, S⊆V(G) and |S|≥2, a tree T in G is called an S-tree if S⊆V(T). Two S-trees T1 and T2 are called internally disjoint if E(T1)∩E(T2)=∅ and V(T1)∩V(T2)=S. For an integer r with 2≤r≤n, the generalizedr-connectivityκr(G) of a graph G is defined as κr(G)=min{κG(S)|S⊆V(G) and |S|=r}, where κG(S) denotes the maximum number k of internally disjoint S-trees in G. In this paper, we consider the generalized 4-connectivity of the line graph L(Km,n) and total graph T(Km,n) of the complete bipartite graph Km,n with 2≤m≤n. The results that κ4(L(Km,n))=m+n−3 for 2≤m≤3 and κ4(L(Km,n))=m+n−4 for m≥4 are obtained by determining κ4(Km×Kn). In addition, we obtain that κ4(T(Km,m))=δ(T(Km,m))−2=2m−2 for m≥2. These results improve the known results about the generalized 3-connectivity of L(Km,n) and T(Km,m) in [Appl. Math. Comput. 347 (2019) 645–652].

Keywords: Generalized connectivity; Line graph; Total graph; Connectivity; Reliability; Graph (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300322000765
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:422:y:2022:i:c:s0096300322000765

DOI: 10.1016/j.amc.2022.126990

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().