The group and the minimal polynomial of a graph |
| |
Authors: | Giovanni Criscuolo Chung-Mo Kwok Abbe Mowshowitz Roberto Tortora |
| |
Affiliation: | Istituto di Fisica Teorica, University of Naples, Naples, Italy;Department of Mathematics, University of British Columbia, Vancouver, Canada;Department of Computer Science, University of British Columbia, Vancouver, Canada;Istituto di Matematica, University of Naples, Naples, Italy |
| |
Abstract: | This paper presents some results linking the minimal polynomial of the adjacency matrix of a graph with its group structure. An upper bound on the order of the group is derived for graphs whose minimal and characteristic polynomials are identical. It is also shown that for a graph with transitive group, the degree of the minimal polynomial is bounded above by the number of orbits of the stabilizer of any given element. Finally, the order of the group of a point-symmetric graph with a prime number of points is shown to depend on the degree of the minimal polynomial, and an algorithm for constructing such a group is given. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|