Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance (Q1343143): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
 
(One intermediate revision by one other user not shown)
Property / cites work
 
Property / cites work: Fractional matchings and covers in infinite hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Packing Problems and Hypergraph Theory: A Survey / rank
 
Normal rank
Property / cites work
 
Property / cites work: Topics on perfect graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3222875 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the computational complexity of upper fractional domination / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3820628 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Fractional Covering Number of Hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3347930 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Contributions to the theory of domination, independence and irredundance in graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Properties of Hereditary Hypergraphs and Middle Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5753985 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Stability, domination and irredundance in a graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Private Neighbor Cube / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximum degree and fractional matchings in uniform hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3328583 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Irredundancy in circular arc graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3032297 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Murky graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Slender graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Alternating orientation and alternating colouration of perfect graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: On slim graphs, even pairs, and star-cutsets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Chordal graphs and upper irredundance, upper domination and independence / rank
 
Normal rank
Property / cites work
 
Property / cites work: A note on graphs which have upper irredundance equal to independence / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3039403 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3682511 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The strong perfect graph conjecture for pan-free graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The validity of the strong perfect-graph conjecture for \((K_4-e)\)-free graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fractional matchings and the Edmonds-Gallai theorem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3218157 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Two classes of perfect graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Strong tree-cographs are Birkhoff graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Coloring perfect \((K_ 4\)-e)-free graphs / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0166-218x(94)90011-6 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1996474894 / rank
 
Normal rank

Latest revision as of 11:08, 30 July 2024

scientific article
Language Label Description Also known as
English
Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance
scientific article

    Statements

    Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance (English)
    0 references
    0 references
    0 references
    1 February 1995
    0 references
    The authors consider finite simple graphs. For such a graph \(G= (V,E)\) the independence number \(\beta (G)\) is the maximum cardinality of a set of non-adjacent vertices. A set \(S\) of vertices is dominating if \(N[ S]= V\); and the upper domination number \(\Gamma (G)\) is the maximum cardinality over all minimal dominating sets. A vertex \(u\in S\subseteq V\) has a private neighbour \(w\) if \(w\in N[ S]\) and \(w\not\in N[S- \{u\}]\), and \(S\) is said to be irredundant if every vertex in \(S\) has a private neighbour. The upper irredundance number \(\text{IR} (G)\) is the maximum cardinality of an irredundant set of \(G\). A function \(f: V\to [0,1]\) is a dominating function if \(f(N [v]) \geq 1\) for each \(v\in V\), where, for a set \(S\) of vertices, \(f(S)= \sum_{v\in S} f(v)\). The dominating function \(f\) is minimal if for every other dominating function \(g\), one has \(f(v)\leq g(v)\) for each \(v\in V\). The maximum of \(f(V)\) over all minimal dominating functions \(f\) is the fractional domination number \(\Gamma_ f (G)\). The authors easily establish that \(\beta (G)\leq \Gamma(G) \leq \Gamma_ f(G)\leq \text{IR} (G)\) and survey the literature on the classes of graphs for which \(\beta (G)= \Gamma(G)= \text{IR} (G)\). The main contribution of the authors is that these equalities hold for the class of strongly perfect graphs. In fact, for strongly perfect graphs equality of the parameters holds not only for \(G\) but for all induced subgraphs of \(G\). It is observed that this stronger property does not hold for tristled graphs and upper bound graphs. The authors then pass on to study classes of graphs for which the equalities do not hold throughout. Among these are claw-free, dart-free, pan-free and \((K_ 4-e)\)-free Berge graphs, and unimodular, slender and slim graphs. All these graphs however satisfy \(\Gamma (G)= \Gamma_ f (G)\). The authors give two examples of graphs for which this equality does not hold. They also prove that if \({\mathcal T}\) is any of these four parameters then \({\mathcal T} (G_ 1+ G_ 2)= \max \{{\mathcal T} (G_ 1), {\mathcal T} (G_ 2)\}\) where \(G_ 1+ G_ 2\) is the join of the graphs \(G_ 1\) and \(G_ 2\).
    0 references
    independence number
    0 references
    upper domination number
    0 references
    dominating sets
    0 references
    upper irredundance number
    0 references
    irredundant set
    0 references
    dominating function
    0 references
    fractional domination number
    0 references
    strongly perfect graphs
    0 references
    join
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers