| Summary: | Let <inline-formula><math display="inline"><semantics><mrow><msub><mi>w</mi><mi>G</mi></msub><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> be the sum of distances from <i>u</i> to all the other vertices of <i>G</i>. The Wiener complexity, <inline-formula><math display="inline"><semantics><mrow><msub><mi>C</mi><mi>W</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, is the number of different values of <inline-formula><math display="inline"><semantics><mrow><msub><mi>w</mi><mi>G</mi></msub><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> in <i>G</i>, and the eccentric complexity, <inline-formula><math display="inline"><semantics><mrow><msub><mi>C</mi><mi>ec</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, is the number of different eccentricities in <i>G</i>. In this paper, we prove that for every integer <i>c</i> there are infinitely many graphs <i>G</i> such that <inline-formula><math display="inline"><semantics><mrow><msub><mi>C</mi><mi>W</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>−</mo><msub><mi>C</mi><mi>ec</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><mi>c</mi></mrow></semantics></math></inline-formula>. Moreover, we prove this statement using graphs with the smallest possible cyclomatic number. That is, if <inline-formula><math display="inline"><semantics><mrow><mi>c</mi><mo>≥</mo><mn>0</mn></mrow></semantics></math></inline-formula> we prove this statement using trees, and if <inline-formula><math display="inline"><semantics><mrow><mi>c</mi><mo><</mo><mn>0</mn></mrow></semantics></math></inline-formula> we prove it using unicyclic graphs. Further, we prove that <inline-formula><math display="inline"><semantics><mrow><msub><mi>C</mi><mi>ec</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≤</mo><mn>2</mn><msub><mi>C</mi><mi>W</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula> if <i>G</i> is a unicyclic graph. In our proofs we use that the function <inline-formula><math display="inline"><semantics><mrow><msub><mi>w</mi><mi>G</mi></msub><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> is convex on paths consisting of bridges. This property also promptly implies the already known bound for trees <inline-formula><math display="inline"><semantics><mrow><msub><mi>C</mi><mi>ec</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≤</mo><msub><mi>C</mi><mi>W</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. Finally, we answer in positive an open question by finding infinitely many graphs <i>G</i> with diameter 3 such that <inline-formula><math display="inline"><semantics><mrow><msub><mi>C</mi><mi>ec</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo><</mo><msub><mi>C</mi><mi>W</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>.
|
|---|