Fractional isomorphism of graphs. (English) Zbl 0808.05077
Authors’ abstract: Let the adjacency matrices of graphs \(G\) and \(H\) be \(A\) and \(B\). These graphs are isomorphic provided there is a permutation matrix \(P\) with \(AP=PB\), or equivalently, \(A=PBP^{\text{T}}\). If we relax the requirement that \(P\) be a permutation matrix, and, instead, require \(P\) only to be doubly stochastic, we arrive at two new equivalence relations on graphs: linear fractional isomorphism (when we relax \(AP=PB\)) and quadratic fractional isomorphism (when we relax \( A=PBP^{\text{T}}\)). Further, if we allow the two instances of \(P\) in \(A=PBP^{\text{T}}\) to be different doubly stochastic matrices, we arrive at the concept of semi-isomorphism. We present necessary and sufficient conditions for graphs to be linearly fractionally isomorphic, we prove that quadratic fractional isomorphism is the same as isomorphism and we relate semi-isomorphism to isomorphism of bipartite graphs.
Reviewer: T.Andreae (Hamburg)
MSC:
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15B51 | Stochastic matrices |
Keywords:
adjacency matrices; permutation matrix; fractional isomorphism; doubly stochastic matrices; semi-isomorphismReferences:
| [1] | Biggs, N., Algebraic Graph Theory (1974), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0284.05101 |
| [2] | Booth, K. S.; Colbourn, C. J., Problems polynomially equivalent to graph isomorphism, (TR CS-77-D4 (1979), Dept. of Comp. Sci., Univ. of Waterloo) |
| [3] | Brightwell, G. R.; Scheinerman, E. R., Fractional dimension of partial order, Order, 9, 139-158 (1992) · Zbl 0773.06001 |
| [4] | Brualdi, R. A., Some applications of doubly stochastic matrices, Linear Algebra Appl., 107, 77-100 (1988) · Zbl 0657.15016 |
| [5] | Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs (1980), VEB Deutscher Verlag der Wissenschaften: VEB Deutscher Verlag der Wissenschaften Berlin · Zbl 0458.05042 |
| [6] | Z. Furedi, Matchings and covers in hypergraphs, Graphs and Combin. 4 (198) 115-206.; Z. Furedi, Matchings and covers in hypergraphs, Graphs and Combin. 4 (198) 115-206. · Zbl 0820.05051 |
| [7] | Hardy, G. H.; Littlewood, J. E.; Pólya, G., Some simple inequalities satisfied by convex functions, Messenger Math., 58, 145-152 (1929) · JFM 55.0740.04 |
| [8] | Horn, R.; Johnson, C., Matrix Analysis (1985), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0576.15001 |
| [9] | Horn, R.; Johnson, C., Topics in Matrix Analysis (1991), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0729.15001 |
| [10] | M. Larsen, J. Propp and D. Ullman, The fractional chromatic number of a graph and a construction of Mycielski, submitted.; M. Larsen, J. Propp and D. Ullman, The fractional chromatic number of a graph and a construction of Mycielski, submitted. · Zbl 0830.05027 |
| [11] | Leighton, F. T., Finite common coverings of graphs, J. Combin. Theory Ser. B, 33, 231-238 (1982) · Zbl 0488.05033 |
| [12] | Manvel, B., On reconstructing graphs, (Ph.D. thesis (1970), University of Michigan: University of Michigan Ann Arbor, MI) · Zbl 0185.27703 |
| [13] | Marshall, A. W.; Olkin, I., Inequalities: Theory of Majorization and its Applications (1979), Academic Press: Academic Press New York · Zbl 0437.26007 |
| [14] | McKay, B. D., Backtrack Programming and the Graph Isomorphism Problem, (M.Sc. thesis (1976), University of Melbourne) |
| [15] | McKay, B. D., Practical graph isomorphism, Cong. Numer., 30, 45-87 (1981) · Zbl 0521.05061 |
| [16] | Mowshowitz, A., The adjacency matrix and the group of a graph, (Harary, F., New Directions in the Theory of Graphs (1973), Academic Press: Academic Press New York), 129-148 · Zbl 0258.05120 |
| [17] | Nash-Williams, C. St. J.A., The reconstruction problem, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory (1978), Academic Press: Academic Press New York), 205-236 · Zbl 0433.05045 |
| [18] | Rado, R., An inequality, J. London Math. Soc., 27, 1-6 (1952) · Zbl 0047.29701 |
| [19] | Schwenk, A. J., Computing the characteristic polynomial of a graph, (Bari, R.; Harary, F., Graphs and Combinatorics, Lecture Notes in Mathematics, Vol. 406 (1974), Springer: Springer Berlin), 153-172 · Zbl 0308.05121 |
| [20] | Schwenk, A. J.; Wilson, R. J., On the eigenvalues of a graph, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory (1978), Academic Press: Academic Press New York), 307-336 · Zbl 0497.05040 |
| [21] | Tinhofer, G., Graph isomorphism and theorems of Birkhoff type, Computing, 36, 285-300 (1986) · Zbl 0581.05038 |
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.
