Wiener Complexity versus the Eccentric Complexity
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>&l...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-12-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/1/79 |
| _version_ | 1797542802296406016 |
|---|---|
| author | Martin Knor Riste Škrekovski |
| author_facet | Martin Knor Riste Škrekovski |
| author_sort | Martin Knor |
| collection | DOAJ |
| description | 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>. |
| first_indexed | 2024-03-10T13:35:39Z |
| format | Article |
| id | doaj.art-3debd7eb88154b859be8402c9485aeef |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T13:35:39Z |
| publishDate | 2020-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-3debd7eb88154b859be8402c9485aeef2023-11-21T07:31:45ZengMDPI AGMathematics2227-73902020-12-01917910.3390/math9010079Wiener Complexity versus the Eccentric ComplexityMartin Knor0Riste Škrekovski1Faculty of Civil Engineering, Slovak University of Technology in Bratislava, Radlinského 11, 81368 Bratislava, SlovakiaFaculty of Mathematics and Physics, University of Ljubljana, 1000 Ljubljana, SloveniaLet <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>.https://www.mdpi.com/2227-7390/9/1/79graphdiameterwiener indextransmissioneccentricity |
| spellingShingle | Martin Knor Riste Škrekovski Wiener Complexity versus the Eccentric Complexity Mathematics graph diameter wiener index transmission eccentricity |
| title | Wiener Complexity versus the Eccentric Complexity |
| title_full | Wiener Complexity versus the Eccentric Complexity |
| title_fullStr | Wiener Complexity versus the Eccentric Complexity |
| title_full_unstemmed | Wiener Complexity versus the Eccentric Complexity |
| title_short | Wiener Complexity versus the Eccentric Complexity |
| title_sort | wiener complexity versus the eccentric complexity |
| topic | graph diameter wiener index transmission eccentricity |
| url | https://www.mdpi.com/2227-7390/9/1/79 |
| work_keys_str_mv | AT martinknor wienercomplexityversustheeccentriccomplexity AT risteskrekovski wienercomplexityversustheeccentriccomplexity |