A unified linear-programming modeling of some topological indices

Hanyuan Deng (), Guihua Huang and Xiaojuan Jiang
Additional contact information
Hanyuan Deng: Hunan Normal University
Guihua Huang: Hunan Normal University
Xiaojuan Jiang: Hunan Normal University

Journal of Combinatorial Optimization, 2015, vol. 30, issue 3, No 25, 826-837

Abstract: Abstract In this paper, we consider an invariant $$I(G)$$ I ( G ) of a graph $$G=(V,E)$$ G = ( V , E ) defined as a summation over all edges, $$I(G) = \sum {c_{ij}x_{ij}}$$ I ( G ) = ∑ c i j x i j where $$c_{ij}$$ c i j and $$x_{ij}$$ x i j is the weight and number, respectively, of edges in $$G$$ G connecting vertices of degree $$i$$ i and $$j$$ j . The graph invariant $$I(G)$$ I ( G ) unifies Randić index, Zagreb index, sum–connectivity index, $$GA_1$$ G A 1 index, ABC index and harmonic index. Based on linear programming methods, we give the extremal values and extremal graphs of $$I(G)$$ I ( G ) among all simple graphs of order $$n$$ n without isolated vertices. Applying this result, we obtain some extremal values of the Randić, Zagreb, sum–connectivity, $$GA_1$$ G A 1 , ABC, and harmonic indices along with the corresponding graphs that obtain these values.

Keywords: Linear programming; Extremal graph; Randić index; Zagreb index; Sum–connectivity index; $$GA_1$$ G A 1 index; ABC index; Harmonic index (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9672-2 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:30:y:2015:i:3:d:10.1007_s10878-013-9672-2

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

DOI: 10.1007/s10878-013-9672-2

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 ().