Results 101 to 110 of about 8,313 (308)
Hereditary Equality of Domination and Exponential Domination
Discussiones Mathematicae Graph Theory, 2018 We characterize a large subclass of the class of those graphs G for which the exponential domination number of H equals the domination number of H for every induced subgraph H of G.
Henning Michael A. +2 more
doaj +1 more source
End-to-End Verification for Subgraph Solving [Elektronisk resurs]
Modern subgraph-finding algorithm implementations consist of thousands of lines of highly optimized code, and this complexity raises questions about their trustworthiness.
Oertel, Andy, +6 more
core +1 more source
Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems [PDF]
, 2012 The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Π, an optimal solution OPT for Π in I and an instance I′ resulting from a local perturbation of I that consists of insertions or removals of a
BORIA, NICOLAS +4 more
core +1 more source
Induced Subgraphs With Many Distinct Degrees [PDF]
Combinatorics, Probability and Computing, 2017 Let hom(G) denote the size of the largest clique or independent set of a graphG. In 2007, Bukh and Sudakov proved that everyn-vertex graphGwith hom(G) =O(logn) contains an induced subgraph with Ω(n1/2) distinct degrees, and raised the question of deciding whether an analogous result holds for everyn-vertex graphGwith hom(G) =O(nϵ), whereϵ> 0 is a ...
Bhargav P. Narayanan, István Tomon
openaire +3 more sources
On the Hardness of Switching to a Small Number of Edges
Journal of Graph Theory, EarlyView.ABSTRACT Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non‐adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching‐equivalent if one can be made isomorphic to the other one by a sequence of switches. Jelínková et al. [DMTCS 13, no. 2, 2011]
Vít Jelínek +2 more
wiley +1 more source
Heavy subgraph pairs for traceability of block-chains
Discussiones Mathematicae Graph Theory, 2014 A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o−1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type ...
Li Binlong +2 more
doaj +1 more source
Reoptimization of maximum weight induced hereditary subgraph problems
, 2017 The reoptimization issue studied in this paper can be described as follows: given aninstance I of some problem Π, an optimal solution O P T for Π in I and an instance I ′ resultingfrom a local perturbation of I that consists of insertions or removals of ...
Monnot, Jérôme +2 more
core +1 more source
Stable Cuts, NAC‐Colourings and Flexible Realisations of Graphs
Journal of Graph Theory, EarlyView.ABSTRACT A (2‐dimensional) realisation of a graph G $G$ is a pair ( G , p ) $(G,p)$, where p $p$ maps the vertices of G $G$ to R 2 ${{\mathbb{R}}}^{2}$. A realisation is flexible if it can be continuously deformed while keeping the edge lengths fixed, and rigid otherwise.
Katie Clinch +5 more
wiley +1 more source
Enumerating Maximal Induced Subgraphs
CoRR, 2020 Given a graph $G$, the maximal induced subgraphs problem asks to enumerate all maximal induced subgraphs of $G$ that belong to a certain hereditary graph class. While its optimization version, known as the minimum vertex deletion problem in literature, has been intensively studied, enumeration algorithms are known for a few simple graph classes, e.g ...
openaire +4 more sources
Weak Degeneracy of Planar Graphs
Journal of Graph Theory, EarlyView.ABSTRACT The weak degeneracy of a graph G $G$ is a numerical parameter that was recently introduced by the first two authors with the aim of understanding the power of greedy algorithms for graph coloring. Every d $d$‐degenerate graph is weakly d $d$‐degenerate, but the converse is not true in general (e.g., all connected d $d$‐regular graphs except ...
Anton Bernshteyn +2 more
wiley +1 more source