The efficiency of AC graphs

DOI10.1016/0166-218X(93)90227-FMaRDI QIDQ686253zbMATH OpenOpenAlexFDO

Authors Jean R. S. Blair

Publication date 28 November 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(93)90227-f

zbMATH Keywords

\(AC\) graphsdominated vertexmaximum efficiency

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

If \(G=(V,e)\) is an undirected graph with a distinguished subset \(R \subset V\), then a vertex \(v \in V \backslash R\) is said to be dominated by \(s \in R\), if \(v\) and \(s\) are connected by an edge. The maximum efficiency \(\varepsilon(G)\) is the maximum number of vertices in \(V \backslash R\) over all subsets \(R \subset V\) that are dominated by exactly one node in \(R\). Expanding a result of \textit{P. J. Bernhard}, \textit{S. T. Hedetniemi} and \textit{D. P. Jacobs} [ibid. 44, 99-108 (1993; Zbl 0780.68097)], the present author constructs a linear time algorithm for computing \(\varepsilon(G)\) when \(G\) is an \(AC\) graph.

Recommendations

• Efficient sets in graphs
• On the efficiency index of a graph
• Efficient sets in partial k-trees
• Efficient edge domination problems in graphs
• scientific article; zbMATH DE number 4085682

Cites work

• Clique graphs and Helly graphs
• Efficient sets in graphs
• scientific article; zbMATH DE number 3884101 (Why is no real title available?)
• scientific article; zbMATH DE number 4095510 (Why is no real title available?)
• NP-completeness of some generalizations of the maximum matching problem
• On the np-completeness of certain network testing problems

Cited in

(5)

• The scattering number of strictly chordal graphs: linear time determination
• New results on Ptolemaic graphs
• A survey on the Intersection graphs of ideals of rings
• Efficient sets in graphs
• Efficient sets in partial k-trees

This page was built for publication: The efficiency of AC graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686253)