×

Extremal irregularity of totally segregated unicyclic graphs. (English) Zbl 1423.05048

Summary: The irregularity of a simple graph \(G=(V,E)\) is defined as \(irr(G)=\sum_{uv\in E(G)}|\mathrm{deg}_G(v)|\), where \(\mathrm{deg}_G(u)\) denotes the degree of a vertex \(u\in V(G)\). A graph in which any two adjacent vertices have distinct degrees is a totally segregated graph. In this paper we determine maximum and minimum of \(\{irr(G): \ G \text{ is a connected totally segregated unicyclic graph with }n \text{ vertices}\}\). Those extremal graphs are also characterised.

MSC:

05C07 Vertex degrees
05C05 Trees
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] H. Abdo, S. Brandt and D. Dimitrov, The total irregularity of a graph, Discrete Mathematics and Theoretical Computer Science 16(1) (2015), 201-206. · Zbl 1288.05130
[2] H. Abdo, N. Cohen and D. Dimitrov, Graphs with maximal irregularity, Filomat 28(7) (2014), 1315-1322. · Zbl 1464.05048
[3] Y. Alavi, G. Chartrand, F. R. K. Chung, P. Erdos, R. L. Graham and O. R. Ollermann, Highly irregular graphs, J. Graph Theory 11 (1987), 235-249. · Zbl 0665.05043
[4] M. O. Albertson, The irregularity of a graph, Ars. Combin. 46 (1997), 219-225. · Zbl 0933.05073
[5] F. K. Bell, A note on the irregularity of graphs, Linear Algebra and its Applications 161 (1992), 45-54. · Zbl 0776.05069
[6] G. Chartrand, P. Erdos and O. R. Ollermann, How to define an irregular graph, College Math. J. 19 (1988), 36-42. · Zbl 0995.05516
[7] G. H. Fath-Tabar, Old and new Zagreb indices of graphs, MATCH Commun. Math. Comput. Chem. 65 (2011), 79-84. · Zbl 1265.05146
[8] G. H. Fath-Tabar, I. Gutman and R. Nasiri, Extremely irregular trees, Bull. Cl. Sci. Math. Nat. Sci. Math. 38 (2013), 1-8. · Zbl 1299.05053
[9] I. Gutman, P. Hansen and H. Melot, Variable neighborhood search for extremal graphs, 10, Comparison of irregularity indices for chemical trees, J. Chem. Inf. Model 45(2) (2005), 222-230 [doi:10.1021/ci0342775].
[10] P. Hansen and H. Mélot, Variable neighborhood search for extremal graphs, IX, Bounding the irregularity of a graph, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 69 (2005), 253-264. · Zbl 1095.05019
[11] M. A. Henning and D. Rautenbach, On the irregularity of bipartite graphs, Discrete Mathematics 307 (2007), 1467-1472. · Zbl 1126.05060
[12] D. E. Jackson and R. Entringer, Totally segregated graphs, Congress. Numer. 55 (1986), 159-165. · Zbl 0633.05060
[13] T. F. Jorry and K. S. Parvathy, Uniformly segregated tree, Bulletin of Kerala Mathematical Association 12(2) (2015), 135-143.
[14] T. F. Jorry and K. S. Parvathy, Minimum total irregularity of totally segregated trees, International Journal of Mathematics Trends and Technology 50(3) (2017), 139-146.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.