On the complexity of some problems related to graph extensions

DOI10.1134/S0001434610110015zbMath1232.05056OpenAlexW2044737433MaRDI QIDQ650325

M. B. Abrosimov

Publication date: 25 November 2011

Published in: Mathematical Notes (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0001434610110015

zbMATH Keywords

fault tolerance\(NP\) problem\(NP\)-complete problemexact \(k\)-extensionextension of graphsirreducible \(k\)-extensionminimal \(k\)-extensionvertex and edge \(k\)-extension

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex degrees (05C07)

Related Items (12)

T-irreducible extension of polygonal digraphs ⋮ Vertex extensions of 4-layer graphs and hypercubes ⋮ Construction of All Minimal Edge Extensions of the Graph with Isomorphism Rejection ⋮ UPPER BOUND FOR THE NUMBER OF ADDITIONAL EDGES IN MINIMAL 1-EDGE EXTENSIONS OF STARLIKE TREES ⋮ T-IRREDUCIBLE EXTENSIONS OF DIRECTED STARLIKE TREES ⋮ ON MINIMAL VERTEX 1-EXTENSIONS OF PATH ORIENTATION ⋮ Construction of All Nonisomorphic Minimal Vertex Extensions of the Graph by the Method of Canonical Representatives ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ About uniqueness of the minimal 1-edge extension of hypercube Q4

Cites Work

• A Graph Model for Fault-Tolerant Computing Systems
• Edge fault tolerance in graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of some problems related to graph extensions