.svg){kind=logo}
ON CO-SEGREGATED GRAPHS
Keywords:
segregated graph, co-segregated graph, minimum size of co-segregated graph, maximum size of co-segregated graph.DOI:
https://doi.org/10.17654/0974165823011Abstract
A connected graph $G$ is totally segregated if every pair of adjacent vertices has distinct degrees. In this article, the class of graphs called co-segregated graphs which are complements of totally segregated graphs is discussed. The maximum size of connected totally segregated graph is found by finding minimum size of a large class of co-segregated graphs. We provide an algorithm to find minimum size of co-segregated graph. A construction of co-segregated graph of order $n$ with minimum size is also described.
Received: October 8, 2022;
Revised: October 30, 2022;
Accepted: January 4, 2023;
References
J. Akiyama, H. Era and F. Harary, The regulation number of a graph, Publ. Inst. Math. (Beograd) 34 (1983), 3-5.
J. Akiyama and F. Harary, Regular graphs containing a given graph, Elem. Math. 38 (1982), 15-17.
Y. Alavi, J. Liu and J. Wang, Highly irregular digraphs, Discrete Math. 111 (1993), 3-10.
M. O. Albertson, The irregularity of a graph, Ars. Combin. 46 (1997), 219-225.
R. Balakrishnan and A. Selvem, k-neighbourhood regular graphs, Proceedings of the National Workshop on Graph Theory and its Applications, 1996, pp. 35-45.
F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, New York, 1990.
Gary Chartrand, Linda Lesniak and Ping Zhang, Graphs and Digraphs, Sixth Edition, A Chapman and Hall Book, Taylor and Francis Group, CRC Press, Boca Raton, London, New York, 2016.
D. E. Jackson and R. Entringer, Totally segregated graphs, Congress. Numer. 55 (1986), 159-165.
Z. Majcher and J. Michael, Degree sequence of highly irregular graphs, Discrete Math. 164 (1997), 225-236.
M. Randic, Characterization of molecular branching, Journal of the American Chemical Society 97 (1975), 6609-6615.
T. F. Jorry, Minimum size of co-segregated graph, Advances and Applications in Discrete Mathematics 32 (2022), 91-112.
D. Rautenbach and I. Schiermeyer, Extremal problems for imbalanced edges, Graphs Comb. 22 (2006), 103-111.
Downloads
Published
Issue
Section
License
Copyright (c) 2023 Pushpa Publishing House, Prayagraj, India
This work is licensed under a Creative Commons Attribution 4.0 International License.
_________________________
Attribution: Credit Pushpa Publishing House as the original publisher, including title and author(s) if applicable.
Contact Pushpa Publishing House for more info or permissions.
Journal Impact Factor: 
