Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
Open Science Slovenia
Open Science
DiKUL
slv
|
eng
Search
Browse
New in RUL
About RUL
In numbers
Help
Sign in
Wiener complexity versus the eccentric complexity
ID
Knor, Martin
(
Author
),
ID
Škrekovski, Riste
(
Author
)
PDF - Presentation file,
Download
(295,50 KB)
MD5: 3638354E474D803F3516197022EBE125
URL - Source URL, Visit
https://www.mdpi.com/2227-7390/9/1/79
Image galllery
Abstract
Let w$_G$(u) be the sum of distances from u to all the other vertices of G. The Wiener complexity, C$_W$(G), is the number of different values of w$_G$(u) in G, and the eccentric complexity, C$_{ec}$(G), is the number of different eccentricities in G. In this paper, we prove that for every integer c there are infinitely many graphs G such that C$_W$(G) – C$_{ec}$(G) = c. Moreover, we prove this statement using graphs with the smallest possible cyclomatic number. That is, if c ≥ 0 we prove this statement using trees, and if c < 0 we prove it using unicyclic graphs. Further, we prove that C$_{ec}$(G) ≤ 2C$_W$(G) − 1 if G is a unicyclic graph. In our proofs we use that the function w$_G$(u) is convex on paths consisting of bridges. This property also promptly implies the already known bound for trees C$_{ec}$(G) ≤ C$_W$(G). Finally, we answer in positive an open question by finding infinitely many graphs G with diameter 3 such that C$_{ec}$(G) < C$_W$(G).
Language:
English
Keywords:
graph
,
diameter
,
Wiener index
,
transmission
,
eccentricity
Work type:
Article
Typology:
1.01 - Original Scientific Article
Organization:
FMF - Faculty of Mathematics and Physics
Publication status:
Published
Publication version:
Version of Record
Year:
2021
Number of pages:
9 str.
Numbering:
Vol. 9, iss. 1, art. 79
PID:
20.500.12556/RUL-134930
UDC:
519.17
ISSN on article:
2227-7390
DOI:
10.3390/math9010079
COBISS.SI-ID:
46211331
Publication date in RUL:
11.02.2022
Views:
752
Downloads:
124
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Copy citation
Share:
Record is a part of a journal
Title:
Mathematics
Shortened title:
Mathematics
Publisher:
MDPI AG
ISSN:
2227-7390
COBISS.SI-ID:
523267865
Licences
License:
CC BY 4.0, Creative Commons Attribution 4.0 International
Link:
http://creativecommons.org/licenses/by/4.0/
Description:
This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
Licensing start date:
01.01.2021
Secondary language
Language:
Slovenian
Keywords:
graf
,
diameter
,
Winerjev indeks
,
transmisija
,
ekscentričnost
Projects
Funder:
ARRS - Slovenian Research Agency
Project number:
P1-0383
Name:
Kompleksna omrežja
Funder:
ARRS - Slovenian Research Agency
Project number:
J1-1692
Name:
Barvanja, dekompozicije in pokritja grafov
Funder:
Other - Other funder or multiple funders
Funding programme:
Slovakia
Project number:
APVV-15-0220
Funder:
Other - Other funder or multiple funders
Funding programme:
Slovakia
Project number:
APVV-17-0428
Funder:
Other - Other funder or multiple funders
Funding programme:
Slovakia, VEGA
Project number:
1/0142/17
Funder:
Other - Other funder or multiple funders
Funding programme:
Slovakia, VEGA
Project number:
1/0238/19
Similar documents
Similar works from RUL:
Similar works from other Slovenian collections:
Back