| Summary: | 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.
|
|---|