𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Two reductions of graph isomorphism to problems on polynomials

✍ Scribed by D. Yu. Grigor'ev

Publisher
Springer US
Year
1982
Tongue
English
Weight
287 KB
Volume
20
Category
Article
ISSN
1573-8795

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the Isomorphism Problem for Finite Ca
On the Isomorphism Problem for Finite Cayley Graphs of Bounded Valency
✍ C.H. Li; C.E. Praeger πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 187 KB

For a subset S of a group G such that 1 / ∈ S and S = S -1 , the associated Cayley graph Cay(G, S) is the graph with vertex set G such that {x, y} is an edge if and only if yx -1 ∈ S. Each Οƒ ∈ Aut(G) induces an isomorphism from Cay(G, S) to the Cayley graph Cay(G, S Οƒ ). For a positive integer m, th

On the isomorphism problem for a family
On the isomorphism problem for a family of cubic metacirculant graphs
✍ Ngo Dac Tan πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 589 KB

In this paper an isomorphism testing algorithm for graphs in the family of all cubic metacirculant graphs with non-empty first symbol So is given. The time complexity of this algorithm is also evaluated.

A solution to Gutman's problem on the ch
A solution to Gutman's problem on the characteristic polynomial of a bipartite graph
✍ Xueliang Li; Heping Zhang πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 209 KB

In this short paper, we present a solution to Gutman's problem on the characteristic polynomial of a bipartite graph (Research Problem 134, Discrete Math. 88 (1991)). In [2] I. Gutman proposed a research problem which is stated as follows. The matchings polynomial of a graph G is defined by cl(G,x)