k-Wiener index of a k-plex

Zhongyuan Che ()
Additional contact information
Zhongyuan Che: Penn State University, Beaver Campus

Journal of Combinatorial Optimization, 2022, vol. 43, issue 1, No 4, 65-78

Abstract: Abstract 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$$ 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 \atopwithdelims ()2} - (n-k) {k+1 \atopwithdelims ()2} $$ 2 1 + ( n - k ) k 2 - ( n - k ) k + 1 2 and above by $$k^2 {n-k+2 \atopwithdelims ()3} - (n-k){k \atopwithdelims ()2}$$ 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$$ ( n - 1 ) 2 and $${n+1 \atopwithdelims ()3}$$ 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.

Keywords: Hereditary hypergraph; k-plex; k-tree; k-Wiener index; Simplicial complex (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00750-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:43:y:2022:i:1:d:10.1007_s10878-021-00750-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00750-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().