Results 1 to 10 of about 59,275 (246)
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
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
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
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 the First-Order Complexity of Induced Subgraph Isomorphism [PDF]
Logical Methods in Computer Science, 2019 Given a graph $F$, let $I(F)$ be the class of graphs containing $F$ as an induced subgraph. Let $W[F]$ denote the minimum $k$ such that $I(F)$ is definable in $k$-variable first-order logic.
Oleg Verbitsky, Maksim Zhukovskii
doaj +2 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
Distinct degrees in induced subgraphs
Proceedings of the American Mathematical Society, 2019 An important theme of recent research in Ramsey theory has been establishing pseudorandomness properties of Ramsey graphs. An N N -vertex graph is called C C -Ramsey if it has no homogeneous set of size C log N C\log N .
Matthew Jenssen +3 more
openalex +5 more sources
Enumerating Maximal Induced Subgraphs
, 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 ...
Yixin Cao
openalex +6 more sources
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 +3 more sources