Isomorphism criterion for monomial graphs
Pages 322 - 328
Abstract
Let q be a prime power, π½q be the field of q elements, and k,βm be positive integers. A bipartite graph Gβ=βGq(k,βm) is defined as follows. The vertex set of G is a union of two copies P and L of two-dimensional vector spaces over π½q, with two vertices (p1,βp2) β P and [ l1,βl2] β L being adjacent if and only if p2β+βl2β=βp <stack>1k</stack>l <stack>1m</stack>. We prove that graphs Gq(k,βm) and Gqβ²(kβ²,βmβ²) are isomorphic if and only if qβ=βqβ² and {gcdβ(k,βqβ-β1), gcdβ(m,βqβ-β1)}β=β{gcdβ(kβ²,βqβ-β1),gcdβ(mβ²,βqβ-β1)} as multisets. The proof is based on counting the number of complete bipartite INFgraphs in the graphs. Β© 2005 Wiley Periodicals, Inc. J Graph Theory 48: 322β328, 2005
- Isomorphism criterion for monomial graphs
Recommendations
New Lower Bounds for Ramsey Numbers of Graphs and Hypergraphs
Let G be an r-uniform hypergraph. The multicolor Ramsey number r"k(G) is the minimum n such that every k-coloring of the edges of the complete r-uniform hypergraph K^(^r^)"n yields a monochromatic copy of G. Improving slightly upon results from M. ...
Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs
AbstractWe investigate the enumeration problems for the class of distance-hereditary graphs and related graph classes. We first give an enumeration algorithm for the class of distance-hereditary graphs using the recent framework for enumerating every non-...
On the isomorphism problem for Helly circular-arc graphs
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular arcs ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
John Wiley & Sons, Inc.
United States
Publication History
Published: 01 April 2005
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
Cited By
View allView Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in