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: Wszystkie pola

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-27 z 27
    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 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ł:
    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ł:
    Deficiency and Forbidden Subgraphs of Connected, Locally-Connected Graphs
    Autorzy:
    Li, Xihe
    Wang, Ligong
    Powiązania:
    https://bibliotekanauki.pl/articles/32083830.pdf
    Data publikacji:
    2020-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    05C40
    05C70
    Opis:
    A graph $G$ is locally-connected if the neighbourhood $ N_G (v) $ induces a connected subgraph for each vertex $v$ in $G$. For a graph $G$, the deficiency of $G$ is the number of vertices unsaturated by a maximum matching, denoted by $ \text{def} (G) $. In fact, the deficiency of a graph measures how far a maximum matching is from being perfect matching. Saito and Xiong have studied subgraphs, the absence of which forces a connected and locally-connected graph $G$ of sufficiently large order to satisfy $ \text{def} (G) \le 1 $. In this paper, we extend this result to the condition of $ \text{def} (G) \le k $, where k is a positive integer. Let $ \beta_0 = \ceil{ 1/2 (3+\sqrt{8k+17} ) } −1 $, we show that $ K_{1,2}, K_{1,3}, . . ., K_{1,β_0}, K_3 $ or \( K_2 \lor 2K_1 \) is the required forbidden subgraph. Furthermore, we obtain some similar results about 3-connected, locally-connected graphs. Key Words: deficiency, locally-connected graph, matching, forbidden subgraph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 1; 195-208
    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ł:
    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ł:
    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ł:
    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ł:
    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ł:
    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ł:
    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ł:
    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ł:
    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ł:
    The Ryjáček Closure and a Forbidden Subgraph
    Autorzy:
    Saito, Akira
    Xiong, Liming
    Powiązania:
    https://bibliotekanauki.pl/articles/31340869.pdf
    Data publikacji:
    2016-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    closure
    claw-free graph
    Hamiltonian graph
    perfect matching
    traceable graph
    Opis:
    The Ryjáček closure is a powerful tool in the study of Hamiltonian properties of claw-free graphs. Because of its usefulness, we may hope to use it in the classes of graphs defined by another forbidden subgraph. In this note, we give a negative answer to this hope, and show that the claw is the only forbidden subgraph that produces non-trivial results on Hamiltonicity by the use of the Ryjáček closure.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 3; 621-628
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Rainbow Vertex-Connection and Forbidden Subgraphs
    Autorzy:
    Li, Wenjing
    Li, Xueliang
    Zhang, Jingshu
    Powiązania:
    https://bibliotekanauki.pl/articles/31342433.pdf
    Data publikacji:
    2018-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    vertex-rainbow path
    rainbow vertex-connection
    forbidden sub-graphs
    Opis:
    A path in a vertex-colored graph is called vertex-rainbow if its internal vertices have pairwise distinct colors. A vertex-colored graph G is rainbow vertex-connected if for any two distinct vertices of G, there is a vertex-rainbow path connecting them. For a connected graph G, the rainbow vertex-connection number of G, denoted by rvc(G), is defined as the minimum number of colors that are required to make G rainbow vertex-connected. In this paper, we find all the families ℱ of connected graphs with |ℱ| ∈ {1, 2}, for which there is a constant kℱ such that, for every connected ℱ-free graph G, rvc(G) ≤ diam(G) + kℱ, where diam(G) is the diameter of G.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 1; 143-154
    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ł:
    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ł:
    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ł:
    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ł:
    Worm Colorings
    Autorzy:
    Goddard, Wayne
    Wash, Kirsti
    Xu, Honghai
    Powiązania:
    https://bibliotekanauki.pl/articles/31339329.pdf
    Data publikacji:
    2015-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    coloring
    rainbow
    monochromatic
    forbidden
    path
    Opis:
    Given a coloring of the vertices, we say subgraph H is monochromatic if every vertex of H is assigned the same color, and rainbow if no pair of vertices of H are assigned the same color. Given a graph G and a graph F, we define an F-WORM coloring of G as a coloring of the vertices of G without a rainbow or monochromatic subgraph H isomorphic to F. We present some results on this concept especially as regards to the existence, complexity, and optimization within certain graph classes. The focus is on the case that F is the path on three vertices.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 3; 571-584
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Vertex Colorings without Rainbow Subgraphs
    Autorzy:
    Goddard, Wayne
    Xu, Honghai
    Powiązania:
    https://bibliotekanauki.pl/articles/31340560.pdf
    Data publikacji:
    2016-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    coloring
    rainbow
    monochromatic
    forbidden
    path
    Opis:
    Given a coloring of the vertices of a graph G, we say a subgraph is rainbow if its vertices receive distinct colors. For a graph F, we define the F-upper chromatic number of G as the maximum number of colors that can be used to color the vertices of G such that there is no rainbow copy of F. We present some results on this parameter for certain graph classes. The focus is on the case that F is a star or triangle. For example, we show that the K3-upper chromatic number of any maximal outerplanar graph on n vertices is [n/2] + 1.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 4; 989-1005
    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ł:
    Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs
    Autorzy:
    Kubicka, Ewa
    Kubicki, Grzegorz
    McKeon, Kathleen A.
    Powiązania:
    https://bibliotekanauki.pl/articles/31339334.pdf
    Data publikacji:
    2015-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    coloring
    sum of colors
    forbidden subgraphs
    Opis:
    Given graphs G and H, a vertex coloring c : V (G) →ℕ is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ (H,G), is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G, ∑(H,G), is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for ∑(H,G), discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, Gk with the property that k more colors than χ (H,G) are required to realize ∑(H,G) for H-free colorings. More complexity results and constructions of graphs requiring extra colors are given for planar and outerplanar graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 3; 541-555
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    \( \mathcal{P} \)-Apex Graphs
    Autorzy:
    Borowiecki, Mieczysław
    Drgas-Burchardt, Ewa
    Sidorowicz, Elżbieta
    Powiązania:
    https://bibliotekanauki.pl/articles/31342421.pdf
    Data publikacji:
    2018-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    induced hereditary classes of graphs
    forbidden subgraphs
    hypergraphs
    transversal number
    Opis:
    Let \( \mathcal{P} \) be an arbitrary class of graphs that is closed under taking induced subgraphs and let \( \mathcal{C}( \mathcal{P} ) \) be the family of forbidden subgraphs for \( \mathcal{P} \). We investigate the class \( \mathcal{P} (k) \) consisting of all the graphs \( G \) for which the removal of no more than \( k \) vertices results in graphs that belong to \( \mathcal{P} \). This approach provides an analogy to apex graphs and apex-outerplanar graphs studied previously. We give a sharp upper bound on the number of vertices of graphs in \( \mathcal{C}( \mathcal{P}(1)) \) and we give a construction of graphs in \( \mathcal{C}( \mathcal{P}(k)) \) of relatively large order for \( k \ge 2 \). This construction implies a lower bound on the maximum order of graphs in \( \mathcal{C}( \mathcal{P}(k)) \). Especially, we investigate \( \mathcal{C}( \mathcal{W}_r(1)) \), where \( \mathcal{W}_r \) denotes the class of \( \mathcal{P}_r \)-free graphs. We determine some forbidden subgraphs for the class \( \mathcal{W}_r(1) \) with the minimum and maximum number of vertices. Moreover, we give sufficient conditions for graphs belonging to \( \mathcal{C} ( \mathcal{P} (k)) \), where \( \mathcal{P} \) is an additive class, and a characterisation of all forests in \( \mathcal{C} ( \mathcal{P} (k)) \). Particularly we deal with \( \mathcal{C} ( \mathcal{P} (1)) \), where \( \mathcal{P} \) is a class closed under substitution and obtain a characterisation of all graphs in the corresponding \( \mathcal{C} ( \mathcal{P} (1)) \). In order to obtain desired results we exploit some hypergraph tools and this technique gives a new result in the hypergraph theory.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 2; 323-349
    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ł:
    Sum-List Colouring of Unions of a Hypercycle and a Path with at Most Two Vertices in Common
    Autorzy:
    Drgas-Burchardt, Ewa
    Sidorowicz, Elżbieta
    Powiązania:
    https://bibliotekanauki.pl/articles/31527293.pdf
    Data publikacji:
    2020-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hypergraphs
    sum-list colouring
    induced hereditary classes
    forbidden hypergraphs
    Opis:
    Given a hypergraph \(\mathcal{H}\) and a function \(f : V (\mathcal{H}) → ℕ\), we say that \(\mathcal{H}\) is $f$-choosable if there is a proper vertex colouring $ϕ$ of \(\mathcal{H}\) such that $ϕ (v) ∈ L(v)$ for all \(v ∈ V (\mathcal{H})\), where \(L : V (\mathcal{H}) → 2^ℕ\) is any assignment of $f(v)$ colours to a vertex $v$. The sum choice number \(\mathcal{H}i_{sc}(\mathcal{H})\) of \(\mathcal{H}\) is defined to be the minimum of \(Σ_{v∈V(\mathcal{H})}f(v)\) over all functions $f$ such that \(\mathcal{H}\) is $f$-choosable. For an arbitrary hypergraph \(\mathcal{H}\) the inequality \(χ_{sc}(\mathcal{H}) ≤ |V (\mathcal{H})| + |ɛ (\mathcal{H})|\) holds, and hypergraphs that attain this upper bound are called $sc$-greedy. In this paper we characterize $sc$-greedy hypergraphs that are unions of a hypercycle and a hyperpath having at most two vertices in common. Consequently, we characterize the hypergraphs of this type that are forbidden for the class of $sc$-greedy hypergraphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 3; 893-917
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-27 z 27

      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