zbMATH — the first resource for mathematics

On the sum of all distances in bipartite graphs. (English) Zbl 1288.05072
Summary: The transmission of a connected graph \(G\) is the sum of all distances between all pairs of vertices in \(G\), it is also called the Wiener index of \(G\). In this paper, sharp bounds on the transmission are determined for several classes of connected bipartite graphs. For example, in the class of all connected \(n\)-vertex bipartite graphs with a given matching number \(q\), the minimum transmission is realized only by the graph \(K_{q,n-q}\); in the class of all connected \(n\)-vertex bipartite graphs of diameter \(d\), the extremal graphs with the minimal transmission are characterized. Moreover, all the extremal graphs having the minimal transmission in the class of all connected \(n\)-vertex bipartite graphs with a given vertex connectivity (resp. edge-connectivity) are also identified.

05C12 Distance in graphs
05C40 Connectivity
Full Text: DOI
[1] Buckley, F.; Harary, F., Distance in graphs, (1990), Addison-Wesley Redwood · Zbl 0688.05017
[2] Cohen, N.; Dimitrov, D.; Krakovski, R.; Škrekovski, R.; Vukašinović, V., On Wiener index of graphs and their line graphs, MATCH Commun. Math. Comput. Chem., 64, 683-698, (2010) · Zbl 1265.05178
[3] Dankelmann, P.; Gutman, I.; Mukwembi, S.; Swart, H. C., The edge-Wiener index of a graph, Discrete Math., 309, 3452-3457, (2009) · Zbl 1188.05059
[4] Dobrynin, A.; Entringer, R.; Gutman, I., Wiener index of trees: theory and applications, Acta Appl. Math., 66, 211-249, (2001) · Zbl 0982.05044
[5] Dobrynin, A.; Gutman, I.; Klavžar, S.; Žigert, P., Wiener index of hexagonal systems, Acta Appl. Math., 72, 247-294, (2002) · Zbl 0993.05059
[6] Don, Y.; Bian, H.; Gao, H.; Yu, H., The polyphenyl chains with extremal edge-Wiener indices, MATCH Commun. Math. Comput. Chem., 64, 757-766, (2010) · Zbl 1265.05573
[7] Elenbogen, B.; Fink, J. F., Distance distributions for graphs modeling computer networks, Discrete Appl. Math., 155, 2612-2624, (2007) · Zbl 1126.05044
[8] Entringer, R. C.; Jackson, D. E.; Snyder, D. A., Distance in graphs, Czechoslovak Math. J., 26, 283-296, (1976) · Zbl 0329.05112
[9] Gutman, I.; Klavžar, S.; Mohar, B., Fiftieth aniversary of the Wiener index, Discrete Appl. Math., 80, 1, 1-113, (1997)
[10] Gutman, I.; Klavžar, S.; Mohar, B., Fifty years of the Wiener index, MATCH Commun. Math. Comput. Chem., 35, 1-259, (1997)
[11] Gutman, I.; Yeh, Y. N.; Lee, S. L.; Luo, Y. L., Some recent results in the theory of the Wiener number, Indian J. Chem. A, 32, 651-661, (1993)
[12] Gutman, I.; Zenkevich, I. G., Wiener index and vibrational energy, Z. Nat.forsch. A, 57, 824-828, (2002)
[13] Harary, F., Status and contrastatus, Sociometry, 22, 233-243, (1959)
[14] Iranmanesh, A.; Kafrani, A. S., Computation of the first edge-Wiener index of \(T U C_4 C_8(S)\) nanotube, MATCH Commun. Math. Comput. Chem., 62, 311-352, (2009)
[15] Liu, M.; Liu, B., On the variable Wiener indices of trees with given maximum degree, Math. Comput. Modelling, 52, 1651-1659, (2010) · Zbl 1205.05073
[16] Luo, W.; Zhou, B., On ordinary and reverse Wiener indices of non-caterpillars, Math. Comput. Modelling, 50, 188-193, (2009) · Zbl 1185.05146
[17] Merris, R., An edge version of the matrix-tree theorem and the Wiener index, Linear Multilinear Algebra, 25, 291-296, (1988) · Zbl 0723.05049
[18] Pisanski, T.; Žerovnik, J., Edge-contributions of some topological indices and arboreality of molecular graphs, Ars Math. Contemp., 2, 49-58, (2009) · Zbl 1175.05043
[19] Plesnik, J., On the sum of all distances in a graph or digraph, J. Graph Theory, 8, 1-21, (1984) · Zbl 0552.05048
[20] Soltes, L., Transmission in graphs: a bound and vertex removing, Math. Slovaca, 41, 11-16, (1991) · Zbl 0765.05097
[21] Wu, B., Wiener index of line graphs, MATCH Commun. Math. Comput. Chem., 64, 699-706, (2010) · Zbl 1265.05522
[22] Zhang, X. D.; Liu, Y.; Han, M. X., Maximum Wiener index of trees with given degree sequence, MATCH Commun. Math. Comput. Chem., 64, 661-682, (2010) · Zbl 1265.05213
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.