JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2022, Vol. 57 ›› Issue (10): 66-71.doi: 10.6040/j.issn.1671-9352.0.2020.683

Previous Articles    

On minimum Steiner k-Wiener index of trees with perfect matching

LAI Jin-hua, LIU Meng-meng*   

  1. School of Mathematics and Science, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China
  • Published:2022-10-06

Abstract: Let G be a connected graph. For 2≤k≤n-1, the Steiner k-Wiener index SWk(G) is defined as SWk(G)=∑S⊆V(G),|S |=kdG(S)where dG(S) is the Steiner distance of S, the edges of the minimum connected tree of vertex set S in G. A lower bound on Steiner k-Wiener index for trees with perfect matching is given and the extremal graph is characterized.

Key words: tree, Steiner k-Wiener index, perfect matching, extremal graph

CLC Number: 

  • O157.5
[1] BONDY J A, MURTY U S R. Graph theory[M]. Berlin: Springer, 2008.
[2] WIENER H. Structural determination of paraffin boiling points[J]. Journal of the American Chemical Society, 1947, 69(1):17-20.
[3] GUTMAN I. Some recent results in the theory of the Wiener number[J]. Indian J Chem, 1993, 32:651-661.
[4] DOBRYNIN A A, Entringer R, Gutman I. Wiener index of trees: theory and applications[J]. Acta Applicandae Mathematica, 2001, 66(3):211-249.
[5] DOBRYNIN A A, GUTMAN I, KLAVZAR S, et al. Wiener index of hexagonal systems[J]. Acta Applicandae Mathematicae, 2002, 72(3):247-294.
[6] HONG Y, LIU H, WU X. On the Wiener index of unicyclic graphs[J]. Hacettepe University Bulletin of Natural Sciences and Engineering Series B: Mathematics and Stats, 2011, 40(1):63-68.
[7] RAMANE H S, REVANKAR D S, GANAGI A B. On the Wiener index of a graph[J]. Journal of the Indonesian Mathematical Society, 2012: 57-66.
[8] CHARTRAND G, OELLERMANN O R, TIAN S L, et al. Steiner distance in graphs[J]. Casopis Pro Pěstování Matematiky, 1989, 114(4):399-410.
[9] GUTMAN I, LI X L, MAO Y P. The Steiner Wiener index of a graph[J]. Discussiones Mathematicae Graph Theory, 2016, 36(2):455.
[10] MAO Y, WANG Z, GUTMAN I. Steiner Wiener index of graph products[J]. Transactions on Combinatorics, 2016, 5(3):39-50.
[11] LU L, HUANG Q X, HOU J X, et al. A sharp lower bound on Steiner Wiener index for trees with given diameter[J]. Discrete Mathematics, 2018, 341(3):723-731.
[12] ZHANG X D, XIANG Q Y. The Wiener index of trees with given degree sequence[J]. MATCH. Communications in Mathematical and in Computer Chemistry, 2008, 60(2):623-644.
[1] QIAN Jin, TANG Da-wei, HONG Cheng-xin. Research on multi-granularity hierarchical sequential three-way decision model [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(9): 33-45.
[2] WU Yi-fan, WANG Guang-fu. Extremal graphs on distance spectral radius of polyomino chains [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(2): 84-91.
[3] CAO Run-feng, LIU Rui-xian, LIU Jing. Reliability analysis of road transportation system of hazardous chemicals tank truck based on fault tree and Bayesian network [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(1): 20-29.
[4] LYU Ning. Dynamics of the stage-structured population system with two kinds of pulses [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(12): 100-110.
[5] WANG Xia, BIAN Hong, YU Hai-zheng. Inverse of Kronecker product of integrally invertible graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(11): 87-92.
[6] MA Hai-feng, YANG Jia-hai, XUE Qing-shui, JU Xing-zhong, ZHU Hao-zhi, LIN Tao, YUAN Xin-xin. A not-same frequency remote data possession checking method [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(5): 81-87.
[7] HE Xiao-li, SHE Yan-hong. Approximate concept and rule acquisition based on attribute granularity [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(5): 13-21.
[8] Chun-hui LING,Ming-zhong ZHANG,Gui-yun LYU,Hao-ran CUI,Pan YAP,Ye WEI,Sheng-yuan LIU,Feng-yun MA,Hua-tian WANG,Xiu-mei LIU,Ling MA. Application impacts analysis on natural forestry management for pine plantation in central and southern mountainous area of Shandong province [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(11): 8-17.
[9] WANG Qian. The contractible edges of a spanning tree and a perfect matching in k-connected graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(8): 29-34.
[10] YANG Zhen-ya, TAI Xiu-guo, CAO Zhen-yu, LI Bo, CAO Bang-hua, WANG Shu-mei, WANG Xuan. A preliminary study on cold resistance of four introduced oaks seedlings [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(5): 43-47.
[11] MA Li-fei, MO Qian, DU Hui. Research on classification for Chinese short film reviews [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(1): 52-57.
[12] TAN Hong-ye, ZHAO Jian, CHEN Qian. Finding potential errors in Chinese treebank based on inconsistencies [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(01): 26-30.
[13] TANG Bo, CHEN Guang, WANG Xing-ya, WANG Fei, CHEN Xiao-hui. Analysis on new word detection and sentiment orientation in Micro-blog [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(01): 20-25.
[14] LU Qi-bei1,2, GUO Fei-peng3. Distributed associative classification algorithm based on improved FP-tree [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(1): 71-75.
[15] LIU Wen-zhuo, CAO Tian-jie, HUANG Shi. An efficient multiple-replica data possession checking scheme [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(09): 160-165.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!