On a Combinatorial Approach to Studying the Steiner Diameter of a Graph and Its Line Graph

Hongfang Liu, Zhizhang Shen, Chenxu Yang and Kinkar Chandra Das ()
Additional contact information
Hongfang Liu: School of Education, Shaanxi Normal University, Xi’an 710062, China
Zhizhang Shen: Department of Computer Science and Technology, Plymouth State University, Plymouth, NH 03264, USA
Chenxu Yang: School of Computer, Qinghai Normal University, Xining 810008, China
Kinkar Chandra Das: Department of Mathematics, Sungkyunkwan University, Suwon 16419, Korea

Mathematics, 2022, vol. 10, issue 20, 1-18

Abstract: In 1989, Chartrand, Oellermann, Tian and Zou introduced the Steiner distance for graphs. This is a natural generalization of the classical graph distance concept. Let Γ be a connected graph of order at least 2, and S \ V ( Γ ) . Then, the minimum size among all the connected subgraphs whose vertex sets contain S is the Steiner distance d Γ ( S ) among the vertices of S . The Steiner k-eccentricity e k ( v ) of a vertex v of Γ is defined by e k ( v ) = max { d Γ ( S ) | S \ V ( Γ ) , | S | = k , a n d v ∈ S } , where n and k are two integers, with 2 ≤ k ≤ n , and the Steiner k-diameter of Γ is defined by sdiam k ( Γ ) = max { e k ( v ) | v ∈ V ( Γ ) } . In this paper, we present an algorithm to derive the Steiner distance of a graph; in addition, we obtain a relationship between the Steiner k -diameter of a graph and its line graph. We study various properties of the Steiner diameter through a combinatorial approach. Moreover, we characterize graph Γ when sdiam k ( Γ ) is given, and we determine sdiam k ( Γ ) for some special graphs. We also discuss some of the applications of Steiner diameter, including one in education networks.

Keywords: Steiner distance; Steiner diameter; line graph; combinatorial thinking; education networks (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/20/3863/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/20/3863/ (text/html)

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:gam:jmathe:v:10:y:2022:i:20:p:3863-:d:945830

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().