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

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-11 z 11
    Tytuł:
    A characterization of 2-tree probe interval graphs
    Autorzy:
    Brown, David E.
    Flesch, Breeann M.
    Lundgren, J. Richard
    Powiązania:
    https://bibliotekanauki.pl/articles/30148257.pdf
    Data publikacji:
    2014-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    interval graph
    probe interval graph
    2-tree
    Opis:
    A graph is a probe interval graph if its vertices correspond to some set of intervals of the real line and can be partitioned into sets P and N so that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. We characterize the 2-trees which are probe interval graphs and extend a list of forbidden induced subgraphs for such graphs created by Pržulj and Corneil in [2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150 (2005) 216-231]
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 3; 509-527
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Phylogeny Graphs of Doubly Partial Orders
    Autorzy:
    Park, Boram
    Sano, Yoshio
    Powiązania:
    https://bibliotekanauki.pl/articles/29551728.pdf
    Data publikacji:
    2013-09-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    competition graph
    phylogeny graph
    doubly partial order
    interval graph
    Opis:
    The competition graph of a doubly partial order is known to be an interval graph. The CCE graph and the niche graph of a doubly partial order are also known to be interval graphs if the graphs do not contain a cycle of length four and three as an induced subgraph, respectively. Phylogeny graphs are variant of competition graphs. The phylogeny graph P(D) of a digraph D is the (simple undirected) graph defined by V (P(D)) := V (D) and E(P(D)) := {xy | N+D (x) ∩ N+D(y) ¹ ⊘ } ⋃ {xy | (x,y) ∈ A(D)}, where N+D(x):= {v ∈ V(D) | (x,v) ∈ A (D)}. In this note, we show that the phylogeny graph of a doubly partial order is an interval graph. We also show that, for any interval graph G̃, there exists an interval graph G such that G̃ contains the graph G as an induced subgraph and that G̃ is the phylogeny graph of a doubly partial order.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 4; 657-664
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs
    Autorzy:
    Immel, Poppy
    Wenger, Paul S.
    Powiązania:
    https://bibliotekanauki.pl/articles/31342143.pdf
    Data publikacji:
    2017-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    distinguishing
    distinguishing number
    list distinguishing
    interval graph
    Opis:
    A distinguishing coloring of a graph G is a coloring of the vertices so that every nontrivial automorphism of G maps some vertex to a vertex with a different color. The distinguishing number of G is the minimum k such that G has a distinguishing coloring where each vertex is assigned a color from {1, . . ., k}. A list assignment to G is an assignment L = {L(v)}v∈V (G) of lists of colors to the vertices of G. A distinguishing L-coloring of G is a distinguishing coloring of G where the color of each vertex v comes from L(v). The list distinguishing number of G is the minimum k such that every list assignment to G in which |L(v)| = k for all v ∈ V (G) yields a distinguishing L-coloring of G. We prove that if G is an interval graph, then its distinguishing number and list distinguishing number are equal.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 1; 165-174
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A reduction of the Graph Reconstruction Conjecture
    Autorzy:
    Monikandan, S.
    Balakumar, J.
    Powiązania:
    https://bibliotekanauki.pl/articles/30148259.pdf
    Data publikacji:
    2014-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    reconstruction
    diameter
    geodetic graph
    interval-regular graph
    Opis:
    A graph is said to be reconstructible if it is determined up to isomorphism from the collection of all its one-vertex deleted unlabeled subgraphs. Reconstruction Conjecture (RC) asserts that all graphs on at least three vertices are reconstructible. In this paper, we prove that interval-regular graphs and some new classes of graphs are reconstructible and show that RC is true if and only if all non-geodetic and non-interval-regular blocks G with diam(G) = 2 or diam(G) = diam(Ḡ) = 3 are reconstructible.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 3; 529-537
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The niche graphs of interval orders
    Autorzy:
    Park, Jeongmi
    Sano, Yoshio
    Powiązania:
    https://bibliotekanauki.pl/articles/30148237.pdf
    Data publikacji:
    2014-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    competition graph
    niche graph
    semiorder
    interval order
    Opis:
    The niche graph of a digraph $D$ is the (simple undirected) graph which has the same vertex set as $D$ and has an edge between two distinct vertices $x$ and $y$ if and only if $N_D^+(x) ∩ N_D^+(y) ≠ ∅ or N_D^−(x) ∩ N_D^−(y) ≠ ∅$, where $N_D^+(x)$ (resp. $N_D^−(x)$) is the set of out-neighbors (resp. in-neighbors) of $x$ in $D$. A digraph $D = (V,A)$ is called a semiorder (or a unit interval order) if there exist a real-valued function $f : V → \mathbb{R}$ on the set $V$ and a positive real number $δ ∈ \mathbb{R}$ such that $(x, y) ∈ A$ if and only if $f(x) > f(y)+δ$. A digraph $D = (V,A)$ is called an interval order if there exists an assignment $J$ of a closed real interval $J(x) ⊂ \mathbb{R}$ to each vertex $x ∈ V$ such that $(x, y) ∈ A$ if and only if $min J(x) > max J(y)$. Kim and Roberts characterized the competition graphs of semiorders and interval orders in 2002, and Sano characterized the competition-common enemy graphs of semiorders and interval orders in 2010. In this note, we give characterizations of the niche graphs of semiorders and interval orders
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 2; 353-359
    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ł:
    Interval Incidence Coloring of Subcubic Graphs
    Autorzy:
    Małafiejska, Anna
    Małafiejski, Michał
    Powiązania:
    https://bibliotekanauki.pl/articles/31341833.pdf
    Data publikacji:
    2017-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    interval incidence coloring
    incidence coloring
    subcubic graph
    Opis:
    In this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is NP-complete, and they asked if Xii(G) ≤ 2Δ(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with Δ(G) = 3.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 2; 427-441
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On Some Properties of Antipodal Partial Cubes
    Autorzy:
    Polat, Norbert
    Powiązania:
    https://bibliotekanauki.pl/articles/31512721.pdf
    Data publikacji:
    2020-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    antipodal graph
    partial cube
    interval monotony
    girth
    diameter
    Opis:
    We prove that an antipodal bipartite graph is a partial cube if and only it is interval monotone. Several characterizations of the principal cycles of an antipodal partial cube are given. We also prove that an antipodal partial cube G is a prism over an even cycle if and only if its order is equal to 4(diam(G) − 1), and that the girth of an antipodal partial cube is less than its diameter whenever it is not a cycle and its diameter is at least equal to 6.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 3; 755-770
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A Note on the Interval Function of a Disconnected Graph
    Autorzy:
    Changat, Manoj
    Hossein Nezhad, Ferdoos
    Mulder, Henry Martyn
    Narayanan, N.
    Powiązania:
    https://bibliotekanauki.pl/articles/31342443.pdf
    Data publikacji:
    2018-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    interval function
    transit function
    axiomatic characterization
    disconnected graph
    Opis:
    In this note we extend the Mulder-Nebeský characterization of the interval function of a connected graph to the disconnected case. One axiom needs to be adapted, but also a new axiom is needed in addition.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 1; 39-48
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Interval edge colorings of some products of graphs
    Autorzy:
    Petrosyan, Petros
    Powiązania:
    https://bibliotekanauki.pl/articles/743918.pdf
    Data publikacji:
    2011
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge coloring
    interval coloring
    regular graph
    products of graphs
    Opis:
    An edge coloring of a graph G with colors 1,2,...,t is called an interval t-coloring if for each i ∈ {1,2,...,t} there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. A graph G is interval colorable, if there is an integer t ≥ 1 for which G has an interval t-coloring. Let ℜ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if G,H ∈ , then the Cartesian product of these graphs belongs to . Also, they formulated a similar problem for the lexicographic product as an open problem. In this paper we first show that if G ∈ , then G[nK₁] ∈ for any n ∈ ℕ. Furthermore, we show that if G,H ∈ and H is a regular graph, then strong and lexicographic products of graphs G,H belong to . We also prove that tensor and strong tensor products of graphs G,H belong to if G ∈ and H is a regular graph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2011, 31, 2; 357-373
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    p-Wiener intervals and p-Wiener free intervals
    Autorzy:
    Kathiresan, Kumarappan
    Arockiaraj, S.
    Powiązania:
    https://bibliotekanauki.pl/articles/743709.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Wiener index of a graph
    Wiener graphical
    p-Wiener interval
    p-Wiener free interval
    hyper-Wiener index of a graph
    radius
    diameter
    Opis:
    A positive integer n is said to be Wiener graphical, if there exists a graph G with Wiener index n. In this paper, we prove that any positive integer n(≠ 2,5) is Wiener graphical. For any positive integer p, an interval [a,b] is said to be a p-Wiener interval if for each positive integer n ∈ [a,b] there exists a graph G on p vertices such that W(G) = n. For any positive integer p, an interval [a,b] is said to be p-Wiener free interval (p-hyper-Wiener free interval) if there exist no graph G on p vertices with a ≤ W(G) ≤ b (a ≤ WW(G) ≤ b). In this paper, we determine some p-Wiener intervals and p-Wiener free intervals for some fixed positive integer p.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 1; 121-127
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-11 z 11

      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