On a characterization of graphs by average labellings

DOI10.7151/DMGT.1046MaRDI QIDQ4209940zbMATH OpenOpenAlexFDO

Authors Matúš Harminc

Publication date 29 December 1998

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/e37821327fe2d0f10d8ad8d2d007158a0986c3d0

zbMATH Keywords

average labelingcharacterizationforestsgraph labelinghereditary graph properties

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

Let \(G=(V,E)\) be a graph. A mapping \(f:V\to N\) is called average labeling if for any \((v_1,v_2),(v_2,v_3)\in E\) one has \(f(v_2)= (f(v_1)+f(v_3))/2\). A labeling is called nontrivial if any connected component of \(G\) (excluding isolated vertices) has at least two differently labeled vertices. The author provides three results towards characterization of hereditary graph properties in terms of average labelings. In particular, all maximal connected subgraphs of \(G\) are exactly paths (i.e. \(G\) is a linear forest) iff there exists a nontrivial average labeling of \(G\). Two remaining results concern characterization of forests and graphs without edges by introducing a bit more complicated average-type labelings.

Recommendations

• Mean labelings of graphs
• On mean labeling of some trees
• Mean trees
• Mean graphs
• Mean labeling of graphs obtained by identifying two graphs

This page was built for publication: On a characterization of graphs by average labellings

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