Publication

On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs

Thomas Liebling
2004
Journal Articles

Abstract

We deal with non-rank facets of the stable set polytope of claw-free graphs. We extend results of Giles and Trotter [7] by (i) showing that for any nonnegative integer a there exists a circulant graph whose stable set polytope has a facet-inducing inequality with (a,a+1)-valued coefficients (rank facets have only coefficients 0, 1), and (ii) providing new facets of the stable set polytope with up to five different non-zero coefficients for claw-free graphs. We prove that coefficients have to be consecutive in any facet with exactly two different non-zero coefficients (assuming they are relatively prime). Last but not least, we present a complete description of the stable set polytope for graphs with stability number 2, already observed by Cook [3] and Shepherd [18].

Official source

https://infoscience.epfl.ch/entities/publication/40288d4b-8395-492f-b74c-7f68589f55b7

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Thomas Liebling
2004
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/40288d4b-8395-492f-b74c-7f68589f55b7

About this result

Related concepts (31)

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree k is called a k‐regular graph or regular graph of degree k. Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree.

Symmetric graph

In the mathematical field of graph theory, a graph G is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices u_1—v_1 and u_2—v_2 of G, there is an automorphism such that and In other words, a graph is symmetric if its automorphism group acts transitively on ordered pairs of adjacent vertices (that is, upon edges considered as having a direction). Such a graph is sometimes also called 1-arc-transitive or flag-transitive. By definition (ignoring u_1 and u_2), a symmetric graph without isolated vertices must also be vertex-transitive.