Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "forbidden subgraph" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 18
Tytuł:
Pairs of forbidden class of subgraphs concerning $K_{1,3}$ and P₆ to have a cycle containing specified vertices
Autorzy:
Sugiyama, Takeshi
Tsugaki, Masao
Powiązania:
https://bibliotekanauki.pl/articles/744494.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
forbidden subgraph
cycle
Opis:
In [3], Faudree and Gould showed that if a 2-connected graph contains no $K_{1,3}$ and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair $K_{1,3}$ and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 3; 645-650
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs
Autorzy:
Liu, Xia
Xiong, Liming
Powiązania:
https://bibliotekanauki.pl/articles/32361726.pdf
Data publikacji:
2022-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
forbidden subgraph
supereulerian
collapsible
Opis:
In this paper, we completely characterize the connected forbidden subgraphs and pairs of connected forbidden subgraphs that force a 2-edge-connected (2-connected) graph to be collapsible. In addition, the characterization of pairs of connected forbidden subgraphs that imply a 2-edge-connected graph of minimum degree at least three is supereulerian will be considered. We have given all possible forbidden pairs. In particular, we prove that every 2-edge-connected noncollapsible (or nonsupereulerian) graph of minimum degree at least three is Z3-free if and only if it is K3-free, where Zi is a graph obtained by identifying a vertex of a K3 with an end-vertex of a Pi+1.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 417-442
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hamiltonian Extendable Graphs
Autorzy:
Yang, Xiaojing
Xiong, Liming
Powiązania:
https://bibliotekanauki.pl/articles/32304150.pdf
Data publikacji:
2022-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian extendable
forbidden subgraph
Opis:
A graph is called Hamiltonian extendable if there exists a Hamiltonian path between any two nonadjacent vertices. In this paper, we give an explicit formula of the minimum number of edges for Hamiltonian extendable graphs and we also characterize the degree sequence for Hamiltonian extendable graphs with minimum number of edges. Besides, we completely characterize the pairs of forbidden subgraphs for 2-connected graphs to be Hamiltonian extendable.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 843-859
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Potential forbidden triples implying hamiltonicity: for sufficiently large graphs
Autorzy:
Faudree, Ralph
Gould, Ronald
Jacobson, Michael
Powiązania:
https://bibliotekanauki.pl/articles/744366.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hamiltonian
forbidden subgraph
claw-free
induced subgraph
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 3; 273-289
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs
Autorzy:
Zheng, Wei
Broersma, Hajo
Wang, Ligong
Powiązania:
https://bibliotekanauki.pl/articles/32361744.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
toughness
forbidden subgraph
Hamilton-connected graph
Hamiltonicity
Opis:
A graph G is called Hamilton-connected if for every pair of distinct vertices {u, v} of G there exists a Hamilton path in G that connects u and v. A graph G is said to be t-tough if t·ω(G − X) ≤ |X| for all X ⊆ V (G) with ω(G − X) > 1. The toughness of G, denoted τ (G), is the maximum value of t such that G is t-tough (taking τ (Kn) = ∞ for all n ≥ 1). It is known that a Hamilton-connected graph G has toughness τ (G) > 1, but that the reverse statement does not hold in general. In this paper, we investigate all possible forbidden subgraphs H such that every H-free graph G with τ (G) > 1 is Hamilton-connected. We find that the results are completely analogous to the Hamiltonian case: every graph H such that any 1-tough H-free graph is Hamiltonian also ensures that every H-free graph with toughness larger than one is Hamilton-connected. And similarly, there is no other forbidden subgraph having this property, except possibly for the graph K1 ∪ P4 itself. We leave this as an open case.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 187-196
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Forbidden Pairs and (k, m)-Pancyclicity
Autorzy:
Crane, Charles Brian
Powiązania:
https://bibliotekanauki.pl/articles/31341696.pdf
Data publikacji:
2017-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hamiltonian
pancyclic
forbidden subgraph
cycle
claw-free
Opis:
A graph G on n vertices is said to be (k,m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ {m, m+1, . . ., n}. This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree, Gould, Jacobson, and Lesniak in 2004. The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. We consider pairs of subgraphs that, when forbidden, guarantee hamiltonicity for 2-connected graphs on n ≥ 10 vertices. There are exactly ten such pairs. For each integer k ≥ 1 and each of eight such subgraph pairs {R, S}, we determine the smallest value m such that any 2-connected {R, S}-free graph on n ≥ 10 vertices is guaranteed to be (k,m)-pancyclic. Examples are provided that show the given values are best possible. Each such example we provide represents an infinite family of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 649-663
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Intersection Dimension and Graph Invariants
Autorzy:
Aravind, N.R.
Subramanian, C.R.
Powiązania:
https://bibliotekanauki.pl/articles/32083820.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
circular dimension
dimensional properties
forbidden-subgraph colorings
Opis:
We show that the intersection dimension of graphs with respect to several hereditary properties can be bounded as a function of the maximum degree. As an interesting special case, we show that the circular dimension of a graph with maximum degree Δ is at most \(O\Big(\Delta\frac{log\Delta}{log log\Delta}\Big)\). It is also shown that permutation dimension of any graph is at most $\Delta(log \Delta)^{1+o(1)}$. We also obtain bounds on intersection dimension in terms of treewidth.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 153-166
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
Autorzy:
Li, Binlong
Broersma, Hajo J.
Zhang, Shenggui
Powiązania:
https://bibliotekanauki.pl/articles/31340596.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
forbidden subgraph
1-tough graph
H-free graph
hamiltonian graph
Opis:
A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K1 ∪ P4 as the only open case.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 915-929
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs with small additive stretch number
Autorzy:
Rautenbach, Dieter
Powiązania:
https://bibliotekanauki.pl/articles/744511.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
stretch number
distance hereditary graph
forbidden induced subgraph
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 2; 291-301
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs without induced P₅ and C₅
Autorzy:
Bacsó, Gabor
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/744580.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph domination
connected domination
complete subgraph
forbidden induced subgraph
characterization
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 503-507
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the 12-Representability of Induced Subgraphs of a Grid Graph
Autorzy:
Chen, Joanna N.
Kitaev, Sergey
Powiązania:
https://bibliotekanauki.pl/articles/32361728.pdf
Data publikacji:
2022-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph representation
12-representable graph
grid graph
forbidden subgraph
square grid graph
line grid graph
Opis:
The notion of a 12-representable graph was introduced by Jones, Kitaev, Pyatkin and Remmel in [Representing graphs via pattern avoiding words, Electron. J. Combin. 22 (2015) #P2.53]. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also that a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al. initiated the study of 12- representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question of Jones et al. is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs. In this paper we answer the question of Jones et al. by providing a complete characterization of 12-representable square grid graphs in terms of forbidden induced subgraphs. Moreover, we conjecture such a characterization for the line grid graphs and give a number of results towards solving this challenging conjecture. Our results are a major step in the direction of characterization of all 12-representable graphs since beyond our characterization, we also discuss relations between graph labelings and 12-representability, one of the key open questions in the area.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 383-403
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Dominating bipartite subgraphs in graphs
Autorzy:
Bacsó, Gábor
Michalak, Danuta
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/744313.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
dominating subgraph
forbidden induced subgraph
bipartite graph
k-partite graph
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 85-94
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graph domination in distance two
Autorzy:
Bacsó, Gábor
Tálos, Attila
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/744316.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
dominating set
connected domination
distance domination
forbidden induced subgraph
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 121-128
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on joins of additive hereditary graph properties
Autorzy:
Drgas-Burchardt, Ewa
Powiązania:
https://bibliotekanauki.pl/articles/743593.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hereditary property
lattice of additive hereditary graph properties
minimal forbidden subgraph family
join in the lattice
Opis:
Let $L^a$ denote a set of additive hereditary graph properties. It is a known fact that a partially ordered set $(L^a, ⊆ )$ is a complete distributive lattice. We present results when a join of two additive hereditary graph properties in $(L^a, ⊆ )$ has a finite or infinite family of minimal forbidden subgraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 3; 413-418
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
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
Powiązania:
https://bibliotekanauki.pl/articles/31342190.pdf
Data publikacji:
2017-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
intersection graph
hypergraph rank
hypergraph multiplicity
forbidden induced subgraph
threshold graph
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 13-28
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 18

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies