Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Discrete Mathematicsarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Discrete Mathematics
Article
License: Elsevier Non-Commercial
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Discrete Mathematics
Article . 2007
License: Elsevier Non-Commercial
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Discrete Mathematics
Article . 2007 . Peer-reviewed
License: Elsevier Non-Commercial
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2007
Data sources: zbMATH Open
DBLP
Article . 2007
Data sources: DBLP
versions View all 5 versions
addClaim

The structure of well-covered graphs with no cycles of length 4

Authors: Jason I. Brown; Richard J. Nowakowski; Igor E. Zverovich;

The structure of well-covered graphs with no cycles of length 4

Abstract

Let \(G\) be a finite, simple graph with vertex set \(V(G)\), let \({I}(G)\) be the set of all maximal independent sets in \(G\) and let \(\alpha(G)=\max\{| I| :I \in {I}(G)\}\) denote the independence number of \(G\). Call \(G\) well-covered if \(| I| =\alpha(G)\) for each \(I \in {I}(G)\). Also let \(f:V(G) \rightarrow \mathbb R\) be a weighting of \(G\) which itself is well-covered if there is some value \(K\) such that \(\sum_{x \in M} f(x) = K\) for each \(M \in {I}(G)\). This paper studies the class WC\((\widehat{C_{4}})\) of well-covered graphs with no cycles of length 4. The main result is that if \(G \in \text{WC}(\widehat{C_{4}})\) then \(V(G)\) can be partitioned, using an equivalence relation, into subsets \(V_{1}, \dots, V_{k}\) such that (i) each induced subgraph \(G[V_{i}]\) is well-covered, (ii) \(\sum_{i=1}^{k} \alpha(G[V_{i}]) = \alpha(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[V_{i}]\), each of which has dimension 1. The 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. The authors give a forbidden co-stable subgraph characterization of graphs in WC\((\widehat{C_{4}})\). Finally, they prove that graphs in WC\((\widehat{C_{4}})\) of bounded maximum generalized degree can be recognized in polynomial time.

Keywords

Forbidden co-stable subgraph., Vector space, Independent set, \(C_4\)-free graph, Theoretical Computer Science, Well-covered weighting, independent set, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Well-covered graph, vector space, Discrete Mathematics and Combinatorics, well-covered graph, well-covered weighting, C4-free graph, forbidden co-stable subgraph

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    19
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
19
Top 10%
Top 10%
Average
hybrid