k-Wiener index of a k-plex

• Published in: Journal of combinatorial optimization 2022, Vol.43 (1), p.65-78
• Main Author: Che, Zhongyuan
• Format: Article
• Language: English
• Subjects: Apexes; Combinatorics; Convex and Discrete Geometry; Graph theory; Graphs; Lower bounds; Mathematical Modeling and Industrial Mathematics; Mathematics; Mathematics and Statistics; Operations Research/Decision Theory; Optimization; Theory of Computation; Trees; Trees (mathematics); Upper bounds
• ISSN: 1382-6905; 1573-2886
• DOI: 10.1007/s10878-021-00750-0

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 ) k 2 - ( n - k ) k + 1 2 and above by k 2 n - k + 2 3 - ( n - k ) k 2 . 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 + 1 3 , 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.