Results 1 to 10 of about 63,637 (247)
Random induced subgraphs of Cayley graphs induced by transpositions [PDF]
Discrete Mathematics, 2009 In this paper we study random induced subgraphs of Cayley graphs of the symmetric group induced by an arbitrary minimal generating set of transpositions.
Emma Yu Jin, Christian M. Reidys
core +7 more sources
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
Induced Subgraphs of the Power of a Cycle [PDF]
SIAM Journal on Discrete Mathematics, 1989 In this article, it is shown that if G is an induced subgraph of the dth power of a cycle of length n, and G has minimum degree $d + k$, then G has at least $[ (d + k)/2d ]n$ vertices. This answers a problem of Kezdy.
J.-C. Bermond, Claudine Peyrat
openalex +5 more sources
Eigenvalue Conditions for Induced Subgraphs [PDF]
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 +2 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 +7 more sources
Forbidden Induced Subgraphs [PDF]
Electronic Notes in Discrete Mathematics, 2017 In descending generality I survey: five partial orderings of graphs, the induced-subgraph ordering, and examples like perfect, threshold, and mock threshold graphs. The emphasis is on how the induced subgraph ordering differs from other popular orderings and leads to different basic questions.
Thomas Zasĺavsky
openalex +4 more sources
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 +7 more sources
Large nearly regular induced subgraphs [PDF]
SIAM Journal on Discrete Mathematics, 2007 For a real c \geq 1 and an integer n, let f(n,c) denote the maximum integer f so that every graph on n vertices contains an induced subgraph on at least f vertices in which the maximum degree is at most c times the minimum degree. Thus, in particular, every graph on n vertices contains a regular induced subgraph on at least f(n,1) vertices. The problem
Noga Alon +2 more
openalex +5 more sources
Induced Subgraph Saturated Graphs
Theory and Applications of Graphs, 2016 A graph $G$ is said to be \emph{$H$-saturated} if $G$ contains no subgraph isomorphic to $H$ but the addition of any edge between non-adjacent vertices in $G$ creates one.
Craig Tennenhouse
doaj +4 more sources
On induced subgraphs of the Hamming graph [PDF]
Journal of Graph Theory, 2020 AbstractIn connection with his solution of the Sensitivity Conjecture, Hao Huang (arXiv: 1907.00847, 2019) asked the following question: Given a graph with high symmetry, what can we say about the smallest maximum degree of induced subgraphs of with vertices, where denotes the size of the largest independent set in ?
Dingding Dong
openalex +5 more sources