Note on irregular graphs
Апстракт
Let G be a graph with vertex set V(G) and edge set E(G). For
v ∈ V(G), by dG(v) is denoted the degree of the vertex v. A graph in which not all vertices
have equal degrees is said to be irregular. Different quantitative measures of irregularity
have been proposed, of which the Albertson index irr(G) = Σuv∈E(G) |dG(u) − dG(v)| is
the most popular. We compare irr(G) with the recently introduced sigma-index σ(G) =
Σuv∈E(G)[dG(u) − dG(v)]2 and show that in the general case these are incomparable.
Graphs in which |dG(u)−dG(v)| = 1 holds for all uv ∈ E(G) are called stepwise irregular
(SI). Severalmethods for constructing SI graphs are described.
Кључне речи:
degree (of vertex) / irregularity (of graph) / stepwise irregular graph / Albertson index / σ indexИзвор:
Bulletin T.CLI de l’Académie serbe des sciences et des arts, 2018, 5-16Издавач:
- Beograd : Académie Serbe des sciences et des arts
Напомена:
- Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles. Sciences mathématiques. 43, 151 (2018).
Gutman, I.,& Réti, T.. (2018). Note on irregular graphs. in Bulletin T.CLI de l’Académie serbe des sciences et des arts Beograd : Académie Serbe des sciences et des arts., 5-16. https://hdl.handle.net/21.15107/rcub_dais_9080
Gutman I, Réti T. Note on irregular graphs. in Bulletin T.CLI de l’Académie serbe des sciences et des arts. 2018;:5-16. https://hdl.handle.net/21.15107/rcub_dais_9080 .
Gutman, Ivan, Réti, Tamás, "Note on irregular graphs" in Bulletin T.CLI de l’Académie serbe des sciences et des arts (2018):5-16, https://hdl.handle.net/21.15107/rcub_dais_9080 .