Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices (Q1309472): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:52, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices |
scientific article |
Statements
Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices (English)
0 references
20 December 1993
0 references
A subset \(X\) of the edge set \(E(G)\) of a graph \(G\) is called independent, if no two edges of \(X\) have an end vertex in common. The set \(X\) is an edge dominating set, if every edge of \(E(G)-X\) has a common end vertex with an edge of \(X\). It is proved that a graph has a unique independent edge dominating set with the minimum number of edges if and only if it has a unique edge dominating set with the minimum number of edges. The structure of graphs with this property is investigated. A particular attention is paid to trees and among them to caterpillars. At the end some operations on graphs are considered in this connection, namely the operation of taking the line graph, of taking the total graph and of taking the corona \(G\circ H\) from given graphs \(G\) and \(H\). All these operations are defined in the paper.
0 references
edge dominating set
0 references
trees
0 references
caterpillars
0 references
line graph
0 references
total graph
0 references