Results 11 to 20 of about 6,576,413 (265)
Isolating highly connected induced subgraphs [PDF]
SIAM Journal on Discrete Mathematics, 2014 We prove that any graph $G$ of minimum degree greater than $2k^2-1$ has a $(k+1)$-connected induced subgraph $H$ such that the number of vertices of $H$ that have neighbors outside of $H$ is at most $2k^2-1$. This generalizes a classical result of Mader,
Penev, Irena +2 more
core +6 more sources
Eigenvalue Conditions for Induced Subgraphs
Discussiones Mathematicae Graph Theory, 2015 Necessary conditions for an undirected graph G to contain a graph H as induced subgraph involving the smallest ordinary or the largest normalized Laplacian eigenvalue of G are presented.
Harant Jochen +2 more
doaj +3 more sources
Detecting induced subgraphs [PDF]
Discrete Applied Mathematics, 2007 An s-graph is a graph with two kinds of edges : subdivisible edges and real edges. A realisation of an s-graphB is any graph obtained by subdividing subdivisible edges of B into paths of arbitrary length (at least one).
Benjamin Lévêque +3 more
core +9 more sources
Planar Induced Subgraphs of Sparse Graphs [PDF]
Journal of Graph Algorithms and Applications, 2014 We show that every graph has an induced pseudoforest of at least n−m/4.5 vertices, an induced partial 2-tree of at least n−m/5 vertices, and an induced planar subgraph of at least n−m/5.2174 vertices. These results are constructive, implying linear-time algorithms to find the respective induced subgraphs.
Glencora Borradaile +2 more
openalex +4 more sources
An induced subgraph of the Hamming graph with maximum degree 1 [PDF]
Journal of Graph Theory, 2021 For every graph G $G$ , let α ( G ) $\alpha (G)$ denote its independence number. What is the minimum of the maximum degree of an induced subgraph of G $G$ with α ( G ) + 1 $\alpha (G)+1$ vertices? We study this question for the n $n$ ‐dimensional Hamming
Vincent Tandya
semanticscholar +1 more source
Induced Subgraphs of Induced Subgraphs of Large Chromatic Number
Combinatorica, 2023 AbstractWe prove that, for every graph F with at least one edge, there is a constant $$c_F$$ c F such that there are graphs of arbitrarily large chromatic number and the same clique number as F in which every F-free induced subgraph has chromatic number at ...
Girao, A +6 more
openaire +4 more sources
On subgraphs without large components [PDF]
Mathematica Bohemica, 2017 We consider, for a positive integer $k$, induced subgraphs in which each component has order at most $k$. Such a subgraph is said to be $k$-divided. We show that finding large induced subgraphs with this property is NP-complete.
Glenn G. Chappell, John Gimbel
doaj +1 more source
Groups for which the noncommuting graph is a split graph [PDF]
International Journal of Group Theory, 2017 The noncommuting graph $nabla (G)$ of a group $G$ is a simple graph whose vertex set is the set of noncentral elements of $G$ and the edges of which are the ones connecting two noncommuting elements. We determine here, up to isomorphism, the structure of
Marzieh Akbari, Alireza Moghaddamfar
doaj +1 more source
A Survey on the Densest Subgraph Problem and its Variants [PDF]
ACM Computing Surveys, 2023 The Densest Subgraph Problem requires us to find, in a given graph, a subset of vertices whose induced subgraph maximizes a measure of density. The problem has received a great deal of attention in the algorithmic literature since the early 1970s, with ...
Tommaso Lanciano +3 more
semanticscholar +1 more source
Reconfiguring spanning and induced subgraphs [PDF]
Theoretical Computer Science, 2018 Subgraph reconfiguration is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertices or sets of edges, satisfying a prescribed graph structure property. Although there has been previous work that can be categorized as subgraph reconfiguration, most of the ...
Tesshu Hanaka +7 more
openaire +4 more sources