کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650982 | 1632444 | 2007 | 11 صفحه PDF | دانلود رایگان |
Let WC(C4^) be the set of well-covered graphs with no cycles of length 4. The main result is that if G∈WC(C4^) then V(G)V(G) can be partitioned, using an equivalence relation, into subsets V1,V2,…,VkV1,V2,…,Vk such that: (i) each G[Vi]G[Vi] is well-covered; (ii) ∑i=1kα(G[Vi])=α(G); and (iii) the vector space of the well-covered weightings of G is the direct sum of the vector spaces of the well-covered weightings of the G[Vi]G[Vi], each of which has dimension 1.Our second result is that the problem of determining whether an edge of a graph is incident with two vertices in the same equivalence class is NP-complete. We give a forbidden co-stable subgraph characterization of graphs in WC(C4^). Finally, we prove that graphs in WC(C4^) of bounded maximum generalized degree can be recognized in polynomial time.
Journal: Discrete Mathematics - Volume 307, Issues 17–18, 6 August 2007, Pages 2235–2245