Temat: induced subgraph - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: Eigenvalue Conditions for Induced Subgraphs
Autorzy:: Harant, Jochen
Niebling, Julia
Richter, Sebastian
Tematy:: induced subgraph
eigenvalue; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31339470.pdf Link otwiera się w nowym oknie
Opis:: 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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: Forbidden triples implying Hamiltonicity: for all graphs
Autorzy:: Faudree, Ralph
Gould, Ronald
Jacobson, Michael
Tematy:: hamiltonian
induced subgraph
forbidden subgraphs; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744414.pdf Link otwiera się w nowym oknie
Opis:: In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with $G_i = K_{1,3}$ for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁, G₂, G₃ such that all G₁G₂G₃-free graphs are hamiltonian.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: Potential forbidden triples implying hamiltonicity: for sufficiently large graphs
Autorzy:: Faudree, Ralph
Gould, Ronald
Jacobson, Michael
Tematy:: hamiltonian
forbidden subgraph
claw-free
induced subgraph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744366.pdf Link otwiera się w nowym oknie
Opis:: In [1], Brousek characterizes all triples of connected graphs, G₁,G₂,G₃, with $G_i = K_{1,3}$ for some i = 1,2, or 3, such that all G₁G₂ G₃-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁,G₂,G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁G₂G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G₁,G₂,G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁,G₂,G₃ such that all G₁G₂G₃-free graphs are hamiltonian. In this paper we consider the question of which triples (including $K_{1,s}$, s ≥ 3) of forbidden subgraphs potentially imply all sufficiently large graphs are hamiltonian. For s ≥ 4 we characterize these families.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Planar Ramsey numbers
Autorzy:: Gorgol, Izolda
Tematy:: Ramsey number
planar graph
induced subgraph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744298.pdf Link otwiera się w nowym oknie
Opis:: The planar Ramsey number PR(G,H) is defined as the smallest integer n for which any 2-colouring of edges of Kₙ with red and blue, where red edges induce a planar graph, leads to either a red copy of G, or a blue H. In this note we study the weak induced version of the planar Ramsey number in the case when the second graph is complete.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: Graphs without induced P₅ and C₅
Autorzy:: Bacsó, Gabor
Tuza, Zsolt
Tematy:: graph domination
connected domination
complete subgraph
forbidden induced subgraph
characterization; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744580.pdf Link otwiera się w nowym oknie
Opis:: Zverovich [Discuss. Math. Graph Theory 23 (2003), 159-162.] has proved that the domination number and connected domination number are equal on all connected graphs without induced P₅ and C₅. Here we show (with an independent proof) that the following stronger result is also valid: Every P₅-free and C₅-free connected graph contains a minimum-size dominating set that induces a complete subgraph.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: Graphs with small additive stretch number
Autorzy:: Rautenbach, Dieter
Tematy:: stretch number
distance hereditary graph
forbidden induced subgraph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744511.pdf Link otwiera się w nowym oknie
Opis:: The additive stretch number $s_{add}(G)$ of a graph G is the maximum difference of the lengths of a longest induced path and a shortest induced path between two vertices of G that lie in the same component of G.We prove some properties of minimal forbidden configurations for the induced-hereditary classes of graphs G with $s_{add}(G) ≤ k$ for some k ∈ N₀ = {0,1,2,...}. Furthermore, we derive characterizations of these classes for k = 1 and k = 2.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 7.

Tytuł:: Dominating bipartite subgraphs in graphs
Autorzy:: Bacsó, Gábor
Michalak, Danuta
Tuza, Zsolt
Tematy:: dominating set
dominating subgraph
forbidden induced subgraph
bipartite graph
k-partite graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744313.pdf Link otwiera się w nowym oknie
Opis:: A graph G is hereditarily dominated by a class of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to . In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: Graph domination in distance two
Autorzy:: Bacsó, Gábor
Tálos, Attila
Tuza, Zsolt
Tematy:: graph
dominating set
connected domination
distance domination
forbidden induced subgraph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744316.pdf Link otwiera się w nowym oknie
Opis:: Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that $Dom Dom _u = Dom₂ _u$ holds for $_u$ = {all connected graphs without induced $P_u$} (u ≥ 2). (In particular, ₂ = {K₁} and ₃ = {all complete graphs}.) Some negative examples are also given.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 9.

Tytuł:: A Ramsey-type theorem for multiple disjoint copies of induced subgraphs
Autorzy:: Nakamigawa, Tomoki
Tematy:: graph decomposition
induced subgraph
graph Ramsey theory
extremal graph theory; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/30148231.pdf Link otwiera się w nowym oknie
Opis:: Let k and ℓ be positive integers with ℓ ≤ k − 2. It is proved that there exists a positive integer c depending on k and ℓ such that every graph of order (2k−1−ℓ/k)n+c contains n vertex disjoint induced subgraphs, where these subgraphs are isomorphic to each other and they are isomorphic to one of four graphs: (1) a clique of order k, (2) an independent set of order k, (3) the join of a clique of order ℓ and an independent set of order k − ℓ, or (4) the union of an independent set of order ℓ and a clique of order k − ℓ.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 10.

Tytuł:: A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs
Autorzy:: Metelsky, Yury
Schemeleva, Kseniya
Werner, Frank
Tematy:: intersection graph
hypergraph rank
hypergraph multiplicity
forbidden induced subgraph
threshold graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31342190.pdf Link otwiera się w nowym oknie
Opis:: We characterize the class $ L_3^2 $ of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from $ L_3^2 $ in the class of threshold graphs, where n is the number of vertices of a tested graph.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "induced subgraph" wg kryterium: Temat