Results 11 to 20 of about 59,275 (246)
Non-adaptive Group Testing on Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 Grebinski and Kucherov (1998) and Alon et al. (2004-2005) study the problem of learning a hidden graph for some especial cases, such as hamiltonian cycle, cliques, stars, and matchings.
Hamid Kameli
doaj +3 more sources
Detecting induced subgraphs [PDF]
Discrete Applied Mathematics, 2007 An \emph{s-graph} is a graph with two kinds of edges: \emph{subdivisible} edges and \emph{real} edges. A \emph{realisation} of an s-graph $B$ is any graph obtained by subdividing subdivisible edges of $B$ into paths of arbitrary length (at least one). Given an s-graph $B$, we study the decision problem $\Pi_B$ whose instance is a graph $G$ and question
Trotignon, Nicolas +3 more
openaire +8 more sources
Isolating Highly Connected Induced Subgraphs [PDF]
SIAM Journal on Discrete Mathematics, 2016 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, which states that a high minimum degree implies the existence of a highly connected subgraph.
Penev, Irena +2 more
openaire +8 more sources
Reoptimization of 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
Nicolas Boria +2 more
openalex +2 more sources
On induced subgraphs of the cube [PDF]
Journal of Combinatorial Theory, Series A, 1988 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Zoltán Füredi +3 more
openaire +2 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
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 +5 more sources
Induced subgraph and eigenvalues of some signed graphs
AKCE International Journal of Graphs and Combinatorics, 2022 Hao Huang proved the Sensitivity Conjecture in [Induced graphs of the hypercube and a proof of the Sensitivity Conjecture, Annals of Mathematics, 190 (2019), 949-955] by signed graph spectral method.
Fu-Tao Hu, Mei-Yu Sun
doaj +1 more source
Induced subgraphs of Johnson graphs [PDF]
Involve, a Journal of Mathematics, 2012 12 pages, 4 ...
Naimi, Ramin, Shaw, Jeffrey
openaire +3 more sources