Graphs with a Fixed Maximum Degree and Order Attaining the Upper Bound on Minimum Status
The status (or transmission) of a vertex in a connected graph is the sum of distances between the vertex and all other vertices. The minimum status (or minimum transmission) of a connected graph is the minimum of the statuses of all vertices in the graph. Previously, sharp lower and upper bounds hav...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-11-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/12/22/3600 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | The status (or transmission) of a vertex in a connected graph is the sum of distances between the vertex and all other vertices. The minimum status (or minimum transmission) of a connected graph is the minimum of the statuses of all vertices in the graph. Previously, sharp lower and upper bounds have been obtained on the minimum status of connected graphs with a fixed maximum degree <i>k</i> and order <i>n</i>. Moreover, for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>2</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mstyle scriptlevel="0" displaystyle="true"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle></mrow></semantics></math></inline-formula>, the following theorem about graphs attaining the maximum on the minimum status has also been proposed without proof. The theorem is as follows: Let <i>G</i> be a connected graph of order n with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>▵</mo><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>=</mo><mi>k</mi></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>2</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mstyle scriptlevel="0" displaystyle="true"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle></mrow></semantics></math></inline-formula>. Then, the minimum status of <i>G</i> attains the maximum if and only if one of the following holds. (1) <i>G</i> is a path or a cycle, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>=</mo><mn>2</mn></mrow></semantics></math></inline-formula>; (2) <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>G</mi><mrow><mi>k</mi><mo>,</mo><mi>n</mi></mrow></msub></semantics></math></inline-formula> is a spanning subgraph of <i>G</i> and <i>G</i> is a spanning subgraph of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>H</mi><mrow><mi>k</mi><mo>,</mo><mi>n</mi></mrow></msub></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>3</mn><mo>≤</mo><mi>k</mi><mo><</mo><mstyle scriptlevel="0" displaystyle="true"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle></mrow></semantics></math></inline-formula>; and (3) either <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>G</mi><mrow><mstyle scriptlevel="0" displaystyle="true"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle><mo>,</mo><mi>n</mi></mrow></msub></semantics></math></inline-formula> is a spanning subgraph of <i>G</i> and <i>G</i> is a spanning subgraph of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>H</mi><mrow><mstyle scriptlevel="0" displaystyle="true"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle><mo>,</mo><mi>n</mi></mrow></msub></semantics></math></inline-formula> or <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>G</mi><mrow><mstyle scriptlevel="0" displaystyle="true"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle><mo>,</mo><mi>n</mi></mrow></msub></semantics></math></inline-formula> is a spanning subgraph of <i>G</i> and <i>G</i> is a spanning subgraph of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>H</mi><mi>n</mi></msub></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>=</mo><mstyle scriptlevel="0" displaystyle="true"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle></mrow></semantics></math></inline-formula> for even <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>6</mn></mrow></semantics></math></inline-formula>. For the integers <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>,</mo><mi>k</mi></mrow></semantics></math></inline-formula> with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>2</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>n</mi><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula>, the graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>G</mi><mrow><mi>k</mi><mo>,</mo><mi>n</mi></mrow></msub></semantics></math></inline-formula> has the vertex set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>V</mi><mrow><mo stretchy="false">(</mo><msub><mi>G</mi><mrow><mi>k</mi><mo>,</mo><mi>n</mi></mrow></msub><mo stretchy="false">)</mo></mrow><mo>=</mo><mrow><mo stretchy="false">{</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><msub><mi>x</mi><mn>2</mn></msub><mo>,</mo><mo>⋯</mo><mo>,</mo><msub><mi>x</mi><mi>n</mi></msub><mo stretchy="false">}</mo></mrow></mrow></semantics></math></inline-formula> and the edge set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>E</mi><mrow><mo stretchy="false">(</mo><msub><mi>G</mi><mrow><mi>k</mi><mo>,</mo><mi>n</mi></mrow></msub><mo stretchy="false">)</mo></mrow><mo>=</mo><mrow><mo stretchy="false">{</mo><msub><mi>x</mi><mi>i</mi></msub><msub><mi>x</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>:</mo><mspace width="0.166667em"></mspace><mi>i</mi><mo>=</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>⋯</mo><mo>,</mo><mi>n</mi><mo>−</mo><mi>k</mi><mo stretchy="false">}</mo></mrow><mo>∪</mo><mrow><mo stretchy="false">{</mo><msub><mi>x</mi><mrow><mi>n</mi><mo>−</mo><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><msub><mi>x</mi><mi>j</mi></msub><mo>:</mo><mspace width="0.166667em"></mspace><mi>j</mi><mo>=</mo><mi>n</mi><mo>−</mo><mi>k</mi><mo>+</mo><mn>2</mn><mo>,</mo><mi>n</mi><mo>−</mo><mi>k</mi><mo>+</mo><mn>3</mn><mo>,</mo><mo>⋯</mo><mo>,</mo><mi>n</mi><mo stretchy="false">}</mo></mrow></mrow></semantics></math></inline-formula>; the graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>H</mi><mrow><mi>k</mi><mo>,</mo><mi>n</mi></mrow></msub></semantics></math></inline-formula> is obtained from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>G</mi><mrow><mi>k</mi><mo>,</mo><mi>n</mi></mrow></msub></semantics></math></inline-formula> by adding all the edges <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>x</mi><mi>i</mi></msub><msub><mi>x</mi><mi>j</mi></msub></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>−</mo><mi>k</mi><mo>+</mo><mn>2</mn><mo>≤</mo><mi>i</mi><mo><</mo><mi>j</mi><mo>≤</mo><mi>n</mi></mrow></semantics></math></inline-formula>; and for even <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>6</mn></mrow></semantics></math></inline-formula> the graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>H</mi><mi>n</mi></msub></semantics></math></inline-formula> is obtained from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>G</mi><mrow><mstyle scriptlevel="0" displaystyle="true"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle><mo>,</mo><mi>n</mi></mrow></msub></semantics></math></inline-formula> by adding the edge <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>x</mi><mrow><mstyle scriptlevel="0" displaystyle="true"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle><mo>−</mo><mn>1</mn></mrow></msub><msub><mi>x</mi><mrow><mstyle scriptlevel="0" displaystyle="true"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle><mo>+</mo><mn>2</mn></mrow></msub></mrow></semantics></math></inline-formula> and all the edges <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>x</mi><mi>i</mi></msub><msub><mi>x</mi><mi>j</mi></msub></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mstyle scriptlevel="0" displaystyle="true"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle><mo>+</mo><mn>3</mn><mo>≤</mo><mi>i</mi><mo><</mo><mi>j</mi><mo>≤</mo><mi>n</mi></mrow></semantics></math></inline-formula>. This study provides the proof to complete the above theorem. |
|---|---|
| ISSN: | 2227-7390 |