Extremal <i>k</i>-Connected Graphs with Maximum Closeness
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 <i>G</i>, the subset <i>S&l...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-11-01
|
| Series: | Axioms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2075-1680/13/12/810 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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 <i>G</i>, the subset <i>S</i> of vertices of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> is called vertex cut of <i>G</i> if the graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>−</mo><mi>S</mi></mrow></semantics></math></inline-formula> becomes disconnected. The minimum cardinality of <i>S</i> for which <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>−</mo><mi>S</mi></mrow></semantics></math></inline-formula> is either disconnected or contains precisely one vertex is called connectivity of <i>G</i>. A graph is called <i>k</i>-connected if it stays connected even when any set of fewer than <i>k</i> vertices is removed. In communication networks, a <i>k</i>-connected graph improves network reliability; even if up to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula> nodes fail, the network remains operational, maintaining connectivity between devices. This paper aims to study the concept of closeness within <i>n</i>-vertex graphs with fixed connectivity. First, we identify the graphs that maximize the closeness among all graphs of order <i>n</i> with fixed connectivity <i>k</i>. Then, we determine the graphs that achieve the maximum closeness within all <i>k</i>-connected graphs of order <i>n</i>, given specific fixed parameters such as diameter, independence number, and minimum degree. |
|---|---|
| ISSN: | 2075-1680 |