In this paper we describe a new characterization of a line-graph G(V,E) in terms of forbidden substructures. Unlike the classical characterization due to Bermond and Meyer based on forbidden induced subgraphs, we rely upon the properties of a suitable maximal stable set S of G. Following Lozin, we say that two nodes u and v in V \ S are similar if N(u) ∩ S = N(v) ∩ S. Moreover, extending a definition due to Schrijver, we say that a node s ∈ S is clique-splittable in G with respect to S if the nodes in N(s) can be partitioned in two cliques (Xs,Ys) with the property that each dissimilar pair of nodes z,y in N(s) is adjacent if and only if both belong to Xs or Ys. Our main result is that a claw-free graph G is a line graph if and only if each node s ∈ S is clique-splittable and S does not define two special structures in G, namely a pair of cross-linked nodes or a free-strip.
A decomposition algorithm for the weighted stable-set problem in claw-free graphs
NOBILI, Paolo;
2012-01-01
Abstract
In this paper we describe a new characterization of a line-graph G(V,E) in terms of forbidden substructures. Unlike the classical characterization due to Bermond and Meyer based on forbidden induced subgraphs, we rely upon the properties of a suitable maximal stable set S of G. Following Lozin, we say that two nodes u and v in V \ S are similar if N(u) ∩ S = N(v) ∩ S. Moreover, extending a definition due to Schrijver, we say that a node s ∈ S is clique-splittable in G with respect to S if the nodes in N(s) can be partitioned in two cliques (Xs,Ys) with the property that each dissimilar pair of nodes z,y in N(s) is adjacent if and only if both belong to Xs or Ys. Our main result is that a claw-free graph G is a line graph if and only if each node s ∈ S is clique-splittable and S does not define two special structures in G, namely a pair of cross-linked nodes or a free-strip.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
