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

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-12 z 12
    Tytuł:
    The smallest nonevasive graph property
    Autorzy:
    Adamaszek, Michał
    Powiązania:
    https://bibliotekanauki.pl/articles/31231990.pdf
    Data publikacji:
    2014-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph properties
    evasiveness
    complexity
    Opis:
    A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to be such, and of the few examples of nontrivial nonevasive properties scattered in the literature the smallest one has n = 6. We exhibit a nontrivial, nonevasive property of 5-vertex graphs and show that it is essentially the unique such with n ≤ 5.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 4; 857-862
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the computational complexity of (O,P)-partition problems
    Autorzy:
    Kratochvíl, Jan
    Schiermeyer, Ingo
    Powiązania:
    https://bibliotekanauki.pl/articles/971956.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    computational complexity
    graph properties
    partition problems
    Opis:
    We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ (i.e., A is independent) and G[B] ∈ P.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 2; 253-258
    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ł:
    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ł:
    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ł:
    Describing Neighborhoods of 5-Vertices in 3-Polytopes with Minimum Degree 5 and Without Vertices of Degrees from 7 to 11
    Autorzy:
    Borodin, Oleg V.
    Ivanova, Anna O.
    Kazak, Olesya N.
    Powiązania:
    https://bibliotekanauki.pl/articles/31342287.pdf
    Data publikacji:
    2018-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    planar graph
    structure properties
    3-polytope
    neighborhood
    Opis:
    In 1940, Lebesgue proved that every 3-polytope contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: (6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11), (5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17), (5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6, ∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11), (5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13). In this paper we prove that every 3-polytope without vertices of degree from 7 to 11 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: (5, 5, 6, 6, ∞), (5, 6, 6, 6, 15), (6, 6, 6, 6, 6), where all parameters are tight.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 3; 615-625
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    All Tight Descriptions of 3-Stars in 3-Polytopes with Girth 5
    Autorzy:
    Borodin, Oleg V.
    Ivanova, Anna O.
    Powiązania:
    https://bibliotekanauki.pl/articles/31342193.pdf
    Data publikacji:
    2017-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    3-polytope
    planar graph
    structure properties
    k -star
    Opis:
    Lebesgue (1940) proved that every 3-polytope P5 of girth 5 has a path of three vertices of degree 3. Madaras (2004) refined this by showing that every P5 has a 3-vertex with two 3-neighbors and the third neighbor of degree at most 4. This description of 3-stars in P5s is tight in the sense that no its parameter can be strengthened due to the dodecahedron combined with the existence of a P5 in which every 3-vertex has a 4-neighbor. We give another tight description of 3-stars in P5s: there is a vertex of degree at most 4 having three 3-neighbors. Furthermore, we show that there are only these two tight descriptions of 3-stars in P5s. Also, we give a tight description of stars with at least three rays in P5s and pose a problem of describing all such descriptions. Finally, we prove a structural theorem about P5s that might be useful in further research.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 1; 5-12
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Generalized ramsey theory and decomposable properties of graphs
    Autorzy:
    Burr, Stefan
    Jacobson, Michael
    Mihók, Peter
    Semanišin, Gabriel
    Powiązania:
    https://bibliotekanauki.pl/articles/744152.pdf
    Data publikacji:
    1999
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary properties
    additivity
    reducibility
    decomposability
    Ramsey number
    graph invariants
    Opis:
    In this paper we translate Ramsey-type problems into the language of decomposable hereditary properties of graphs. We prove a distributive law for reducible and decomposable properties of graphs. Using it we establish some values of graph theoretical invariants of decomposable properties and show their correspondence to generalized Ramsey numbers.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1999, 19, 2; 199-217
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Describing Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree 6 or 7
    Autorzy:
    Batueva, Ts.Ch-D.
    Borodin, O.V.
    Ivanova, A.O.
    Nikiforov, D.V.
    Powiązania:
    https://bibliotekanauki.pl/articles/32361718.pdf
    Data publikacji:
    2022-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    planar graph
    structural properties
    3-polytope
    5-star
    neighborhood
    Opis:
    In 1940, in attempts to solve the Four Color Problem, Henry Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P5 of 3-polytopes with minimum degree 5. This description depends on 32 main parameters. (6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11), (5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17), (5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6, ∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11), (5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13) Not many precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in P5. In 2018, Borodin, Ivanova, Kazak proved that every forbidding vertices of degree from 7 to 11 results in a tight description (5, 5, 6, 6, ∞), (5, 6, 6, 6, 15), (6, 6, 6, 6, 6). Recently, Borodin, Ivanova, and Kazak proved every 3-polytope in P5 with no vertices of degrees 6, 7, and 8 has a 5-vertex whose neighborhood is majorized by one of the sequences (5, 5, 5, 5, ∞) and (5, 5, 10, 5, 12), which is tight and improves a corresponding description (5, 5, 5, 5, ∞), (5, 5, 9, 5, 17), (5, 5, 10, 5, 14), (5, 5, 11, 5, 13) that follows from the Lebesgue Theorem. The purpose of this paper is to prove that every 3-polytope with minimum degree 5 and no vertices of degree 6 or 7 has a 5-vertex whose neighborhood is majorized by one of the ordered sequences (5, 5, 5, 5, ∞), (5, 5, 8, 5, 14), or (5, 5, 10, 5, 12).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 2; 535-548
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    More About the Height of Faces in 3-Polytopes
    Autorzy:
    Borodin, Oleg V.
    Bykov, Mikhail A.
    Ivanova, Anna O.
    Powiązania:
    https://bibliotekanauki.pl/articles/31342325.pdf
    Data publikacji:
    2018-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    plane map
    planar graph
    3-polytope
    structural properties
    height of face
    Opis:
    The height of a face in a 3-polytope is the maximum degree of its incident vertices, and the height of a 3-polytope, h, is the minimum height of its faces. A face is pyramidal if it is either a 4-face incident with three 3-vertices, or a 3-face incident with two vertices of degree at most 4. If pyramidal faces are allowed, then h can be arbitrarily large, so we assume the absence of pyramidal faces in what follows. In 1940, Lebesgue proved that every quadrangulated 3-polytope has h ≤ 11. In 1995, this bound was lowered by Avgustinovich and Borodin to 10. Recently, Borodin and Ivanova improved it to the sharp bound 8. For plane triangulation without 4-vertices, Borodin (1992), confirming the Kotzig conjecture of 1979, proved that h ≤ 20, which bound is sharp. Later, Borodin (1998) proved that h ≤ 20 for all triangulated 3-polytopes. In 1996, Horňák and Jendrol’ proved for arbitrarily polytopes that h ≤ 23. Recently, Borodin and Ivanova obtained the sharp bounds 10 for trianglefree polytopes and 20 for arbitrary polytopes. In this paper we prove that any polytope has a face of degree at most 10 with height at most 20, where 10 and 20 are sharp.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 2; 443-453
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Light Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No 6-Vertices
    Autorzy:
    Borodin, Oleg V.
    Ivanova, Anna O.
    Vasil’eva, Ekaterina I.
    Powiązania:
    https://bibliotekanauki.pl/articles/31348169.pdf
    Data publikacji:
    2020-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    planar map
    planar graph
    3-polytope
    structural properties
    5-star
    weight
    height
    Opis:
    In 1940, Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P5 of 3-polytopes with minimum degree 5. Given a 3-polytope P, by w(P) denote the minimum of the degree-sum (weight) of the neighborhoods of 5-vertices (minor 5-stars) in P. In 1996, Jendrol’ and Madaras showed that if a polytope P in P5 is allowed to have a 5-vertex adjacent to four 5-vertices, then w(P) can be arbitrarily large. For each P in P5 without vertices of degree 6 and 5-vertices adjacent to four 5-vertices, it follows from Lebesgue’s Theorem that w(P) ≤ 68. Recently, this bound was lowered to w(P) ≤ 55 by Borodin, Ivanova, and Jensen and then to w(P) ≤ 51 by Borodin and Ivanova. In this note, we prove that every such polytope P satisfies w(P) ≤ 44, which bound is sharp.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 4; 985-994
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Low 5-Stars at 5-Vertices in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree from 7 to 9
    Autorzy:
    Borodin, Oleg V.
    Bykov, Mikhail A.
    Ivanova, Anna O.
    Powiązania:
    https://bibliotekanauki.pl/articles/31348144.pdf
    Data publikacji:
    2020-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    planar map
    planar graph
    3-polytope
    structural properties
    5-star
    weight
    height
    Opis:
    In 1940, Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class $P_5$ of 3-polytopes with minimum degree 5. Given a 3-polytope $P$, by $h_5(P)$ we denote the minimum of the maximum degrees (height) of the neighborhoods of 5-vertices (minor 5-stars) in $P$. Recently, Borodin, Ivanova and Jensen showed that if a polytope $P$ in $P_5$ is allowed to have a 5-vertex adjacent to two 5-vertices and two more vertices of degree at most 6, called a (5, 5, 6, 6, ∞)-vertex, then $h_5(P)$ can be arbitrarily large. Therefore, we consider the subclass \(P_5^\ast\) of 3-polytopes in $P_5$ that avoid (5, 5, 6, 6, ∞)-vertices. For each $P^\ast$ in $P_5^\ast$ without vertices of degree from 7 to 9, it follows from Lebesgue’s Theorem that $h_5(P^\ast) ≤ 17$. Recently, this bound was lowered by Borodin, Ivanova, and Kazak to the sharp bound $h_5(P^\ast) ≤ 15$ assuming the absence of vertices of degree from 7 to 11 in $P^\ast$. In this note, we extend the bound $h_5(P^\ast) ≤ 15$ to all $P^\ast$s without vertices of degree from 7 to 9.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 4; 1025-1033
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-12 z 12

      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