Graph decomposition with constraints in the minimum degree (Q1102305)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Graph decomposition with constraints in the minimum degree
scientific article

    Statements

    Graph decomposition with constraints in the minimum degree (English)
    0 references
    0 references
    1988
    0 references
    In the paper are investigated decompositions of finite simple graph G with minimum degree \(\delta\) (G)\(\geq \delta (n\equiv \delta (mod 2))\) n denotes the cardinality of V(G). Let max(k,G) denote the set of all k- subsets \(A\subseteq V(G)\) such that the number of edges in the induced subgraph \(<A>\) is a maximum. All subsets of max(k,G) are called dense sets. It is proved that for some \(i\in \{0,1,...,1/2\}\) there exists a partition (X,Y) of V(G) such that (i) \(| X| =\lceil (1/2)n\rceil +i\), \(| Y| =\lfloor n/2\rfloor -i,\) (ii) \(\delta (X)\geq \lceil \delta /2\rceil +i\), \(\delta\) (Y)\(\geq \lfloor \delta /2\rfloor -i,\) (iii) X or Y is dense in G. Two subsets of V(G) form a weak (i,\(\delta)\) partition if condition (i) and (ii) are fulfilled. There are formulated some conjectures concerning weak decomposability of graphs.
    0 references
    graph decomposition
    0 references
    minimum degree
    0 references
    dense sets
    0 references

    Identifiers