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 graph" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-15 z 15
    Tytuł:
    Forbidden Structures for Planar Perfect Consecutively Colourable Graphs
    Autorzy:
    Borowiecka-Olszewska, Marta
    Drgas-Burchardt, Ewa
    Powiązania:
    https://bibliotekanauki.pl/articles/31341980.pdf
    Data publikacji:
    2017-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge colouring
    consecutive (interval) colouring
    deficiency
    Sevastjanov graph
    forbidden graph
    Opis:
    A consecutive colouring of a graph is a proper edge colouring with posi- tive integers in which the colours of edges incident with each vertex form an interval of integers. The idea of this colouring was introduced in 1987 by Asratian and Kamalian under the name of interval colouring. Sevast- janov showed that the corresponding decision problem is NP-complete even restricted to the class of bipartite graphs. We focus our attention on the class of consecutively colourable graphs whose all induced subgraphs are consecutively colourable, too. We call elements of this class perfect consecutively colourable to emphasise the conceptual similarity to perfect graphs. Obviously, the class of perfect consecutively colourable graphs is induced hereditary, so it can be characterized by the family of induced forbidden graphs. In this work we give a necessary and sufficient conditions that must be satisfied by the generalized Sevastjanov rosette to be an induced forbid- den graph for the class of perfect consecutively colourable graphs. Along the way, we show the exact values of the deficiency of all generalized Sevastjanov rosettes, which improves the earlier known estimating result. It should be mentioned that the deficiency of a graph measures its closeness to the class of consecutively colourable graphs. We motivate the investigation of graphs considered here by showing their connection to the class of planar perfect consecutively colourable graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 2; 315-336
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties
    Autorzy:
    Drgas-Burchardt, Ewa
    Powiązania:
    https://bibliotekanauki.pl/articles/743169.pdf
    Data publikacji:
    2009
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary graph property
    lattice of additive hereditary graph properties
    minimal forbidden graph family
    join in the lattice
    reducibility
    Opis:
    An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let $L^a$ denote a class of all such properties. In the paper, we consider H-reducible over $L^a$ properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2009, 29, 2; 263-274
    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ł:
    Forbidden configurations for hypohamiltonian graphs
    Autorzy:
    Fabrici, I.
    Madaras, T.
    Timkova, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/256013.pdf
    Data publikacji:
    2018
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    hypohamiltonian graph
    forbidden configuration
    long cycle
    Opis:
    A graph G is called hypohamiltonian if G is not hamiltonian, but G — x is hamiltonian for each vertex x of G. We present a list of 331 forbidden configurations which do not appear in hypohamiltonian graphs.
    Źródło:
    Opuscula Mathematica; 2018, 38, 3; 357-377
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Minimal forbidden subgraphs of reducible graph properties
    Autorzy:
    Berger, Amelie
    Powiązania:
    https://bibliotekanauki.pl/articles/743439.pdf
    Data publikacji:
    2001
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    reducible graph properties
    forbidden subgraphs
    induced subgraphs
    Opis:
    A property of graphs is any class of graphs closed under isomorphism. Let ₁,₂,...,ₙ be properties of graphs. A graph G is (₁,₂,...,ₙ)-partitionable if the vertex set V(G) can be partitioned into n sets, {V₁,V₂,..., Vₙ}, such that for each i = 1,2,...,n, the graph $G[V_i] ∈ _i$. We write ₁∘₂∘...∘ₙ for the property of all graphs which have a (₁,₂,...,ₙ)-partition. An additive induced-hereditary property is called reducible if there exist additive induced-hereditary properties ₁ and ₂ such that = ₁∘₂. Otherwise is called irreducible. An additive induced-hereditary property can be defined by its minimal forbidden induced subgraphs: those graphs which are not in but which satisfy that every proper induced subgraph is in . We show that every reducible additive induced-hereditary property has infinitely many minimal forbidden induced subgraphs. This result is also seen to be true for reducible additive hereditary properties.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2001, 21, 1; 111-117
    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ł:
    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ł:
    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ł
    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ł:
    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ł:
    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ł:
    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ł:
    Heavy subgraph pairs for traceability of block-chains
    Autorzy:
    Li, Binlong
    Broersma, Hajo
    Zhang, Shenggui
    Powiązania:
    https://bibliotekanauki.pl/articles/30148234.pdf
    Data publikacji:
    2014-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    block-chain traceable graph
    Ore-type condition
    forbidden subgrap
    $o_{−1}$-heavy subgraph
    Opis:
    A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is $o_{−1}$-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least $n−1$ in $G$. A block-chain is a graph whose block graph is a path, i.e., it is either a $P_1$, $P_2$, or a 2-connected graph, or a graph with at least one cut vertex and exactly two end-blocks. Obviously, every traceable graph is a block-chain, but the reverse does not hold. In this paper we characterize all the pairs of connected $o_{−1}$-heavy graphs that guarantee traceability of block-chains. Our main result is a common extension of earlier work on degree sum conditions, forbidden subgraph conditions and heavy subgraph conditions for traceability
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 2; 287-307
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Game-Perfect Semiorientations of Forests
    Autorzy:
    Andres, Stephan Dominique
    Charpentier, Clément
    Fong, Wai Lam
    Powiązania:
    https://bibliotekanauki.pl/articles/32361719.pdf
    Data publikacji:
    2022-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    game chromatic number
    game-perfect digraph
    forest
    dichromatic number
    game-perfect graph
    forbidden induced subdigraph
    Opis:
    We consider digraph colouring games where two players, Alice and Bob, alternately colour vertices of a given digraph D with a colour from a given colour set in a feasible way. The game ends when such move is not possible any more. Alice wins if every vertex is coloured at the end, otherwise Bob wins. The smallest size of a colour set such that Alice has a winning strategy is the game chromatic number of D. The digraph D is game-perfect if, for every induced subdigraph H of D, the game chromatic number of H equals the size of the largest symmetric clique of H. In the strong game, colouring a vertex is feasible if its colour is different from the colours of its in-neighbours. In the weak game, colouring a vertex is feasible unless it creates a monochromatic directed cycle. There are six variants for each game, which specify the player who begins and whether skipping is allowed for some player. For all six variants of both games, we characterise the class of game-perfect semiorientations of forests by a set of forbidden induced subdigraphs and by an explicit structural description.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 2; 501-534
    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ł
      Wyświetlanie 1-15 z 15

      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