Results 31 to 40 of about 331 (182)
Graph Classes Generated by Mycielskians
Discussiones Mathematicae Graph Theory, 2020 In this paper we use the classical notion of weak Mycielskian M′(G) of a graph G and the following sequence: M′0(G) = G, M′1(G) = M′(G), and M′n(G) = M′(M′n−1(G)), to show that if G is a complete graph of order p, then the above sequence is a generator ...
Borowiecki Mieczys law +3 more
doaj +1 more source
Some Variations of Perfect Graphs
Discussiones Mathematicae Graph Theory, 2016 We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively.
Dettlaff Magda +3 more
doaj +1 more source
Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph
SIAM Journal on Discrete Mathematics, 2022 Accepted manuscript, see DOI for journal ...
Sepehr Hajebi, Yanjia Li, Sophie Spirkl
openaire +3 more sources
Forbidden induced subgraph characterization of circle graphs within split graphs [PDF]
Discrete Applied Mathematics, 2022 A graph is circle if its vertices are in correspondence with a family of chords in a circle in such a way that every two distinct vertices are adjacent if and only if the corresponding chords have nonempty intersection. Even though there are diverse characterizations of circle graphs, a structural characterization by minimal forbidden induced subgraphs
Flavia Bonomo-Braberman +3 more
openaire +4 more sources
Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs [PDF]
The Computer Journal, 2015 24 pages, An extended abstract of this paper will appear in the proceedings of CIAC ...
Konrad K. Dabrowski, Daniël Paulusma
openalex +7 more sources
Theory and Applications of GraphsA class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G.
Jagdeep Singh +2 more
doaj +1 more source
Characterizing the forbidden pairs for graphs to be super-edge-connected
AKCE International Journal of Graphs and CombinatoricsLet [Formula: see text] be a set of given connected graphs. A graph G is said to be [Formula: see text]-free if G contains no H as an induced subgraph for any [Formula: see text].
Hazhe Ye, Yingzhi Tian
doaj +1 more source
Small clique number graphs with three trivial critical ideals
Special Matrices, 2018 The critical ideals of a graph are the determinantal ideals of the generalized Laplacian matrix associated to a graph. Previously, they have been used in the understanding and characterizing of the graphs with critical group with few invariant factors ...
Alfaro Carlos A., Valencia Carlos E.
doaj +1 more source
Forbidden induced subgraphs for near perfect matchings
Discrete Mathematics, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Ota, Katsuhiro +2 more
openaire +2 more sources
Finding Maximum Weight 2‐Packing Sets on Arbitrary Graphs
Networks, EarlyView.ABSTRACT A 2‐packing set for an undirected, weighted graph G=(V,E,w)$$ G=\left(V,\kern0.3em E,\kern0.3em w\right) $$ is a subset 𝒮⊆V such that any two vertices v1,v2∈𝒮 are not adjacent and have no common neighbors. The Maximum Weight 2‐Packing Set problem that asks for a 2‐packing set of maximum weight is NP$$ \mathbf{NP} $$‐hard. Next to 13 novel data
Jannick Borowitz +2 more
wiley +1 more source