Moments in graphs

DOI10.1016/J.DAM.2012.10.024MaRDI QIDQ1946217zbMATH OpenOpenAlexFDO

Authors C. Dalfó, E. Garriga, Miquel Angel Fiol

Publication date 18 April 2013

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.5615

zbMATH Keywords

adjacency matrixgraft productmomenttopological index

Mathematics Subject Classification ID

Distance in graphs (05C12) Signed and weighted graphs (05C22) Graph polynomials (05C31) Extremal problems in graph theory (05C35)

Abstract: Let $G$ be a connected graph with vertex set $V$ and a {em weight function} $ho$ that assigns a nonnegative number to each of its vertices. Then, the {em $ho$-moment} of $G$ at vertex $u$ is defined to be $M_G^{ho}(u)=su{m}_{vinV}ho(v)dist(u,v)$, where $dist(cdot,cdot)$ stands for the distance function. Adding up all these numbers, we obtain the {em $ho$-moment of $G$}: ${\displaystyle }$ M_G^{ ho}=sum_{uin V}M_G^{ ho}(u)=1/2sum_{u,vin V}dist(u,v)[ ho(u)+ ho(v)]. ${\displaystyle }$ This parameter generalizes, or it is closely related to, some well-known graph invariants, such as the {em Wiener index} $W(G)$, when $ho(u)=1/2$ for every $uinV$, and the {em degree distance} $D^{\prime }(G)$, obtained when $ho(u)=delta(u)$, the degree of vertex $u$. In this paper we derive some exact formulas for computing the $ho$-moment of a graph obtained by a general operation called graft product, which can be seen as a generalization of the hierarchical product, in terms of the corresponding $ho$-moments of its factors. As a consequence, we provide a method for obtaining nonisomorphic graphs with the same $ho$-moment for every $ho$ (and hence with equal mean distance, Wiener index, degree distance, etc.). In the case when the factors are trees and/or cycles, techniques from linear algebra allow us to give formulas for the degree distance of their product.

Recommendations

• The \(\rho\)-moments of vertex-weighted graphs
• Vertex-weightings for distance moments and thorny graphs
• Wiener-type invariants of some graph operations
• scientific article; zbMATH DE number 3972909
• On the Wiener index of rooted product of graphs

Cited in

(3)

• The \(\rho\)-moments of vertex-weighted graphs
• Vertex-weightings for distance moments and thorny graphs
• scientific article; zbMATH DE number 434881 (Why is no real title available?)

This page was built for publication: Moments in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1946217)