Classes of interval graphs under expanding length restrictions | Zendy

Fishburn P. C. | Zendy; Graham R. L. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Classes of interval graphs under expanding length restrictions

Author(s) -

Fishburn P. C.,

Graham R. L.

Publication year - 1985

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.3190090405

Subject(s) - mathematics , combinatorics , bipartite graph , isomorphism (crystallography) , interval (graph theory) , discrete mathematics , intersection (aeronautics) , prime (order theory) , indifference graph , upper and lower bounds , graph , mathematical analysis , chemistry , crystal structure , engineering , crystallography , aerospace engineering

Let C (α) denote the finite interval graphs representable as intersection graphs of closed real intervals with lengths in [1, α]. The points of increase for C are the rational α ≥ 1. The set D (α) = [∩ β>α C (β)]\ C (α) of graphs that appear as soon as we go past α is characterized up to isomorphism on the basis of finite sets E (α) of irreducible graphs for each rational α. With α = p / q and p and q relatively prime, ∣ E (α)∣ is computed for all ( p,q ) with q ⩽ 2 and p = q + 1. When q = 1, E(p ) contains only the bipartite star K 1 , p +2. A lowr bound on ∣ E (α)∣ is given for all rational α.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research