scientific article

Stephen T. Hedetniemi, Sandra M. Hedetniemi

Publication date: 1977

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

trees independent set of edges dominating set of edges

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

Related Items (57)

Perfect edge domination and efficient edge domination in graphs ⋮ Vertex-Edge Roman Domination ⋮ RESTRAINED EDGE DOMINATION IN GRAPHS ⋮ Edge domination in Boolean function graph B(L(G), NINC) of a graph ⋮ Edge domination in complete partite graphs ⋮ Approximation hardness of edge dominating set problems ⋮ Edge domatic numbers of complete \(n\)-partite graphs ⋮ On the algorithmic complexity of edge total domination ⋮ Line domination in graphs ⋮ Minimum maximal matchings in cubic graphs ⋮ On the domination number of a graph and its block graph ⋮ On independent \([1, 2\)-sets in trees] ⋮ On coefficients of edge domination polynomial of a graph ⋮ RESTRAINED TOTAL EDGE DOMINATION IN THE JOIN OF GRAPHS ⋮ PERFECT EDGE DOMINATION IN GRAPHS ⋮ On well-edge-dominated graphs ⋮ Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs ⋮ Roman edge semi-total block domination of a graph ⋮ Line-set domination in graphs ⋮ Common domination perfect graphs ⋮ An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem ⋮ Nordhaus-Gaddum-type results on the connected edge domination number ⋮ EDGE ITALIAN DOMINATION OF SOME GRAPH PRODUCTS ⋮ 2-(edge-)connected edge domination number and matching number ⋮ Edge domination in some path and cycle related graphs ⋮ Approximability of the capacitated \(b\)-edge dominating set problem ⋮ On graphs with equal domination and independent domination numbers ⋮ Edge domination on bipartite permutation graphs and cotriangulated graphs ⋮ Generalizing the induced matching by edge capacity constraints ⋮ A note on an induced subgraph characterization of domination perfect graphs ⋮ Integer programming formulations for the minimum weighted maximal matching problem ⋮ Linear time algorithms for generalized edge dominating set problems ⋮ The algorithmic complexity of mixed domination in graphs ⋮ Unnamed Item ⋮ The complexity of total edge domination and some related results on trees ⋮ Complexity and characterization aspects of edge-related domination for graphs ⋮ Edges contained in all or in no minimum edge dominating set of a tree ⋮ Domination in distance-hereditary graphs ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ Linear algorithms on recursive representations of trees ⋮ Unnamed Item ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem ⋮ \(k\)-tuple domination in graphs ⋮ On domination and independent domination numbers of a graph ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ EDGE DOMINATION AND TOTAL EDGE DOMINATION IN THE CORONA OF GRAPHS ⋮ Rainbow edge domination numbers in graphs ⋮ On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem ⋮ A note on the edge Roman domination in trees ⋮ Dominating sets for split and bipartite graphs ⋮ Bounds on total edge domination number of a tree ⋮ Edge domination and 2-independence in trees ⋮ A 2-approximation algorithm for the minimum weight edge dominating set problem ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET ⋮ The edge-to-edge geodetic domination number of a graph

This page was built for publication: