Vol. 39, No. 2, 1971

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 304: 1  2
Vol. 303: 1  2
Vol. 302: 1  2
Vol. 301: 1  2
Vol. 300: 1  2
Vol. 299: 1  2
Vol. 298: 1  2
Vol. 297: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Editorial Board
Subscriptions
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Author Index
To Appear
 
Other MSP Journals
Matrix characterizations of circular-arc graphs

Alan Curtiss Tucker

Vol. 39 (1971), No. 2, 535–545
Abstract

A graph G is a circular-arc graph if there is a one-to-one correspondence between the vertices of G and a family of arcs on a circle such that two distinct vertices are adjacent when the corresponding arcs intersect. Circular-arc graphs are characterized as graphs whose adjacency matrix has the quasi-circular 1’s property. Two interesting subclasses of circular-arc graphs are also discussed proper circular-arc graphs and graphs whose augmented adjacency matrix has the circular 1’s property.

Mathematical Subject Classification 2000
Primary: 05C99
Milestones
Received: 30 April 1970
Published: 1 November 1971
Authors
Alan Curtiss Tucker