About AutoGraphiX Conjecture on Domination Number and Remoteness of Graphs
A set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>D</mi><mo>⊆</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></s...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-10-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/10/19/3706 |
| _version_ | 1797478043260813312 |
|---|---|
| author | Lidan Pei |
| author_facet | Lidan Pei |
| author_sort | Lidan Pei |
| collection | DOAJ |
| description | A set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>D</mi><mo>⊆</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> is called a dominating set if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mo>[</mo><mi>v</mi><mo>]</mo><mo>∩</mo><mi>D</mi><mo>≠</mo><mo>∅</mo></mrow></semantics></math></inline-formula> for every vertex <i>v</i> in graph <i>G</i>. The domination number <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>γ</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> is the minimum cardinality of a dominating set of <i>G</i>. The proximity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>π</mi><mo>(</mo><mi>v</mi><mo>)</mo></mrow></semantics></math></inline-formula> of a vertex <i>v</i> is the average distance from it to all other vertices in graph. The remoteness <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>ρ</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> of a connected graph <i>G</i> is the maximum proximity of all the vertices in graph <i>G</i>. AutoGraphiX Conjecture A.565 gives the sharp upper bound on the difference between the domination number and remoteness. In this paper, we characterize the explicit graphs that attain the upper bound in the above conjecture, and prove the improved AutoGraphiX conjecture. |
| first_indexed | 2024-03-09T21:26:25Z |
| format | Article |
| id | doaj.art-42e5c74bbc964261b7ad4efcdd146450 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T21:26:25Z |
| publishDate | 2022-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-42e5c74bbc964261b7ad4efcdd1464502023-11-23T21:06:06ZengMDPI AGMathematics2227-73902022-10-011019370610.3390/math10193706About AutoGraphiX Conjecture on Domination Number and Remoteness of GraphsLidan Pei0School of Mathematics and Statistics, Hefei Normal University, Hefei 230601, ChinaA set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>D</mi><mo>⊆</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> is called a dominating set if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mo>[</mo><mi>v</mi><mo>]</mo><mo>∩</mo><mi>D</mi><mo>≠</mo><mo>∅</mo></mrow></semantics></math></inline-formula> for every vertex <i>v</i> in graph <i>G</i>. The domination number <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>γ</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> is the minimum cardinality of a dominating set of <i>G</i>. The proximity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>π</mi><mo>(</mo><mi>v</mi><mo>)</mo></mrow></semantics></math></inline-formula> of a vertex <i>v</i> is the average distance from it to all other vertices in graph. The remoteness <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>ρ</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> of a connected graph <i>G</i> is the maximum proximity of all the vertices in graph <i>G</i>. AutoGraphiX Conjecture A.565 gives the sharp upper bound on the difference between the domination number and remoteness. In this paper, we characterize the explicit graphs that attain the upper bound in the above conjecture, and prove the improved AutoGraphiX conjecture.https://www.mdpi.com/2227-7390/10/19/3706AutoGraphiX conjecturedomination numberremoteness |
| spellingShingle | Lidan Pei About AutoGraphiX Conjecture on Domination Number and Remoteness of Graphs Mathematics AutoGraphiX conjecture domination number remoteness |
| title | About AutoGraphiX Conjecture on Domination Number and Remoteness of Graphs |
| title_full | About AutoGraphiX Conjecture on Domination Number and Remoteness of Graphs |
| title_fullStr | About AutoGraphiX Conjecture on Domination Number and Remoteness of Graphs |
| title_full_unstemmed | About AutoGraphiX Conjecture on Domination Number and Remoteness of Graphs |
| title_short | About AutoGraphiX Conjecture on Domination Number and Remoteness of Graphs |
| title_sort | about autographix conjecture on domination number and remoteness of graphs |
| topic | AutoGraphiX conjecture domination number remoteness |
| url | https://www.mdpi.com/2227-7390/10/19/3706 |
| work_keys_str_mv | AT lidanpei aboutautographixconjectureondominationnumberandremotenessofgraphs |