Graph classes characterized both by forbidden subgraphs and degree sequences |
| |
| Authors: | Michael D. Barrus Mohit Kumbhat Stephen G. Hartke |
| |
| Affiliation: | 1. Department of Mathematics, University of Illinois, Urbana, Illinois 61801;2. Department of Mathematics, University of Nebraska, Lincoln, Nebraska 68588 |
| |
| Abstract: | Given a set  of graphs, a graph G is  ‐free if G does not contain any member of  as an induced subgraph. We say that  is a degree‐sequence‐forcing set if, for each graph G in the class  of  ‐free graphs, every realization of the degree sequence of G is also in  . We give a complete characterization of the degree‐sequence‐forcing sets  when  has cardinality at most two. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 131–148, 2008 |
| |
| Keywords: | degree‐sequence‐forcing set forbidden subgraphs degree sequence characterization 2‐switch potentially P‐graphic forcibly P‐graphic |
|
|
