| Title |
Extremal k-connected graphs with maximum closeness / |
| Authors |
Hayat, Fazal ; Otera, Daniele Ettore |
| DOI |
10.3390/axioms13120810 |
| Full Text |
|
| Is Part of |
Axioms.. Basel : MDPI. 2024, vol. 13, iss. 12, art. no. 810, p. [1-10].. eISSN 2075-1680 |
| Keywords [eng] |
closeness ; connectivity ; k-connected graph ; diameter ; independence number ; minimum degree |
| Abstract [eng] |
Closeness is a measure that quantifies how quickly information can spread from a given node to all other nodes in the network, reflecting the efficiency of communication within the network by indicating how close a node is to all other nodes. For a graph G, the subset S of vertices of 𝑉(𝐺) is called vertex cut of G if the graph 𝐺−𝑆 becomes disconnected. The minimum cardinality of S for which 𝐺−𝑆 is either disconnected or contains precisely one vertex is called connectivity of G. A graph is called k-connected if it stays connected even when any set of fewer than k vertices is removed. In communication networks, a k-connected graph improves network reliability; even if up to 𝑘−1 nodes fail, the network remains operational, maintaining connectivity between devices. This paper aims to study the concept of closeness within n-vertex graphs with fixed connectivity. First, we identify the graphs that maximize the closeness among all graphs of order n with fixed connectivity k. Then, we determine the graphs that achieve the maximum closeness within all k-connected graphs of order n, given specific fixed parameters such as diameter, independence number, and minimum degree. |
| Published |
Basel : MDPI |
| Type |
Journal article |
| Language |
English |
| Publication date |
2024 |
| CC license |
|
