TY - JOUR

T1 - k-Wiener index of a k-plex

AU - Che, Zhongyuan

N1 - Funding Information:
The research work is supported by the Research Development Grant (RDG) from Penn State University, Beaver Campus.
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2021

Y1 - 2021

N2 - A k-plex is a hypergraph with the property that each subset of a hyperedge is also a hyperedge and each hyperedge contains at most k+ 1 vertices. We introduce a new concept called the k-Wiener index of a k-plex as the summation of k-distances between every two hyperedges of cardinality k of the k-plex. The concept is different from the Wiener index of a hypergraph which is the sum of distances between every two vertices of the hypergraph. We provide basic properties for the k-Wiener index of a k-plex. Similarly to the fact that trees are the fundamental 1-dimensional graphs, k-trees form an important class of k-plexes and have many properties parallel to those of trees. We provide a recursive formula for the k-Wiener index of a k-tree using its property of a perfect elimination ordering. We show that the k-Wiener index of a k-tree of order n is bounded below by 2(1+(n-k)k2)-(n-k)(k+12) and above by k2(n-k+23)-(n-k)(k2). The bounds are attained only when the k-tree is a k-star and a k-th power of path, respectively. Our results generalize the well-known results that the Wiener index of a tree of order n is bounded between (n- 1) 2 and (n+13), and the lower bound (resp., the upper bound) is attained only when the tree is a star (resp., a path) from 1-dimensional trees to k-dimensional trees.

AB - A k-plex is a hypergraph with the property that each subset of a hyperedge is also a hyperedge and each hyperedge contains at most k+ 1 vertices. We introduce a new concept called the k-Wiener index of a k-plex as the summation of k-distances between every two hyperedges of cardinality k of the k-plex. The concept is different from the Wiener index of a hypergraph which is the sum of distances between every two vertices of the hypergraph. We provide basic properties for the k-Wiener index of a k-plex. Similarly to the fact that trees are the fundamental 1-dimensional graphs, k-trees form an important class of k-plexes and have many properties parallel to those of trees. We provide a recursive formula for the k-Wiener index of a k-tree using its property of a perfect elimination ordering. We show that the k-Wiener index of a k-tree of order n is bounded below by 2(1+(n-k)k2)-(n-k)(k+12) and above by k2(n-k+23)-(n-k)(k2). The bounds are attained only when the k-tree is a k-star and a k-th power of path, respectively. Our results generalize the well-known results that the Wiener index of a tree of order n is bounded between (n- 1) 2 and (n+13), and the lower bound (resp., the upper bound) is attained only when the tree is a star (resp., a path) from 1-dimensional trees to k-dimensional trees.

UR - http://www.scopus.com/inward/record.url?scp=85105349390&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85105349390&partnerID=8YFLogxK

U2 - 10.1007/s10878-021-00750-0

DO - 10.1007/s10878-021-00750-0

M3 - Article

AN - SCOPUS:85105349390

SN - 1382-6905

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

ER -