This is a preview of subscription content, log in via an institution to check access.
REFERENCES
R. Barbosa and D. M. Cardoso, “On regular-stable graphs,” Ars Comb. (to appear).
O. Bastert, “Computing equitable partitions of graphs,” MATCH-Commun. Math. Comput. Chem. 40, 265–272 (1999).
D. M. Cardoso, “Convex quadratic programming approach to the maximum matching problem,” J. Glob. Optim. 21, 91–106 (2001).
M. Doob, “An intersection between line graphs, eigenvalues, and matroids,” J. Comb. Theory, Ser. B 15, 40–50 (1973).
M. Doob, “A surprising property of the least eigenvalue of a graph,” Linear Algebra Appl. 46, 1–7 (1982).
J. R. Edmonds, “Paths, trees, and flowers,” Can. J. Math., 17, 449–467 (1965).
C. D. Godsil, Algebraic Combinatorics, Chapman & Hall, New York (1993).
M. M. Halldórsson, J. Kratochvíl, and J. A. Telle, “Independent sets with domination constraints,” Discr. Appl. Math. 99, 39–54 (2000).
R. M. Karp, “Reducibility among combinatorial problems,” In: Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, Eds.), Plenum Press, New York (1972), pp. 85–104.
L. Lovász, “An algorithm theory of numbers, graphs and convexity,” SIAM, Regional Conf. Ser. Appl. Math., Philadelphia (1986).
V. V. Lozin, “Stability in P 5 and banner-free graphs,” Eur. J. Oper. Res. 125, 292–297 (2000).
C. Luz, “An upper bound on the independence number of a graph computable in polynomial-time,” Oper. Res. Lett. 18, 139–145 (1995).
G. J. McKay, Backtrack programming and the graph isomorphism problem, M.Sci. Thesis, University of Melbourne (1976).
B. D. Minty, “On maximal independent sets of vertices in claw-free graphs,” J. Comb. Theory, Ser. B, 28, 284–304 (1980).
R. Mosca, “Stable sets in certain P 6-free graphs,” Discr. Appl. Math. 92, 177–191 (1999).
M. Muzychuk and M. Klin, “On graphs with three eigenvalues,” Discr. Math. 189, 191–207 (1998).
D. L. Powers and M. M. Sulaiman, “The walk partition and colorations of a graph,” Linear Algebra Appl. 48, 145–159 (1982).
H. Sachs, “Über Teiler, Faktoren und charakteristische Polynome von Graphen, I,” Wiss. Z. 12, 7–12 (1966).
H. Sachs, “Über Teiler, Faktoren und charakteristische Polynome von Graphen, II,” Wiss. Z. 13, 405–412 (1967).
A. J. Schwenk, “Computing the characteristic polynomial of a graph,” In: Graphs and Combinatorics (R. Bari and F. Harary, Eds.), Springer-Verlag, Berlin (1974), pp. 153–172.
N. Sbihi, “Algorithm de recherche d'un stable de cardinalité maximum dans un graphe sans étoile,” Discr. Math. 29, 53–76 (1980).
P. F. Stadler and G. Tinhofer, “Equitable partitions, coherent algebras and random walks: Applications to the correlation structure of landscapes,” MATCH-Commun. Math. Comput Chem. 40, 215–261 (1999).
J. A. Telle, “Characterization of domination-type parameters in graphs,” Congr. Numerantium 94, 9–16 (1993).
Rights and permissions
About this article
Cite this article
Cardoso, D.M., Rama, P.C. Equitable Bipartitions of Graphs and Related Results. Journal of Mathematical Sciences 120, 869–880 (2004). https://doi.org/10.1023/B:JOTH.0000013552.96026.87
Issue Date:
DOI: https://doi.org/10.1023/B:JOTH.0000013552.96026.87