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

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-12 z 12
    Tytuł:
    Maxclique and unit disk characterizations of strongly chordal graphs
    Autorzy:
    Caria, Pablo De
    McKee, Terry A.
    Powiązania:
    https://bibliotekanauki.pl/articles/30148683.pdf
    Data publikacji:
    2014-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    chordal graph
    strongly chordal graph
    clique
    maxclique
    closed neighborhood
    Opis:
    Maxcliques (maximal complete subgraphs) and unit disks (closed neighborhoods of vertices) sometime play almost interchangeable roles in graph theory. For instance, interchanging them makes two existing characterizations of chordal graphs into two new characterizations. More intriguingly, these characterizations of chordal graphs can be naturally strengthened to new characterizations of strongly chordal graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 3; 593-602
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Strongly pancyclic and dual-pancyclic graphs
    Autorzy:
    McKee, Terry
    Powiązania:
    https://bibliotekanauki.pl/articles/743097.pdf
    Data publikacji:
    2009
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    pancyclic graph
    cycle extendable
    chordal graph
    pancyclic matroid
    dual-chordal graph
    Opis:
    Say that a cycle C almost contains a cycle C¯ if every edge except one of C¯ is an edge of C. Call a graph G strongly pancyclic if every nontriangular cycle C almost contains another cycle C¯ and every nonspanning cycle C is almost contained in another cycle C⁺. This is equivalent to requiring, in addition, that the sizes of C¯ and C⁺ differ by one from the size of C. Strongly pancyclic graphs are pancyclic and chordal, and their cycles enjoy certain interpolation and extrapolation properties with respect to almost containment. Much of this carries over from graphic to cographic matroids; the resulting 'dual-pancyclic' graphs are shown to be exactly the 3-regular dual-chordal graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2009, 29, 1; 5-14
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The i-chords of cycles and paths
    Autorzy:
    McKee, Terry
    Powiązania:
    https://bibliotekanauki.pl/articles/743264.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    chord
    chordal graph
    strongly chordal graph
    ptolemaic graph
    trivially perfect graph
    threshold graph
    Opis:
    An i-chord of a cycle or path is an edge whose endpoints are a distance i ≥ 2 apart along the cycle or path. Motivated by many standard graph classes being describable by the existence of chords, we investigate what happens when i-chords are required for specific values of i. Results include the following: A graph is strongly chordal if and only if, for i ∈ {4,6}, every cycle C with |V(C)| ≥ i has an (i/2)-chord. A graph is a threshold graph if and only if, for i ∈ {4,5}, every path P with |V(P)| ≥ i has an (i -2)-chord.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 4; 607-615
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Strongly Unichord-Free Graphs
    Autorzy:
    McKee, Terry A.
    Powiązania:
    https://bibliotekanauki.pl/articles/31343449.pdf
    Data publikacji:
    2019-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    unichord-free graph
    strongly chordal graph
    Opis:
    Several recent papers have investigated unichord-free graphs—the graphs in which no cycle has a unique chord. This paper proposes a concept of strongly unichord-free graph, defined by being unichord-free with no cycle of length 5 or more having exactly two chords. In spite of its overly simplistic look, this can be regarded as a natural strengthening of unichordfree graphs—not just the next step in a sequence of strengthenings—and it has a variety of characterizations. For instance, a 2-connected graph is strongly unichord-free if and only if it is complete bipartite or complete or “minimally 2-connected” (defined as being 2-connected such that deleting arbitrary edges always leaves non-2-connected subgraphs).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2019, 39, 2; 365-374
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A New Characterization of Unichord-Free Graphs
    Autorzy:
    McKee, Terry A.
    Powiązania:
    https://bibliotekanauki.pl/articles/31234070.pdf
    Data publikacji:
    2015-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    chordal graph
    unichord-free graph
    minimal separator
    Opis:
    Unichord-free graphs are defined as having no cycle with a unique chord. They have appeared in several papers recently and are also characterized by minimal separators always inducing edgeless subgraphs (in contrast to characterizing chordal graphs by minimal separators always inducing complete subgraphs). A new characterization of unichord-free graphs corresponds to a suitable reformulation of the standard simplicial vertex characterization of chordal graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 4; 765-771
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The leafage of a chordal graph
    Autorzy:
    Lin, In-Jen
    McKee, Terry
    West, Douglas
    Powiązania:
    https://bibliotekanauki.pl/articles/972051.pdf
    Data publikacji:
    1998
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    chordal graph
    subtree intersection representation
    leafage
    Opis:
    The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes. The maximum of l(G) on n-vertex graphs is n - lg n - 1/2 lg lg n + O(1). The proper leafage l*(G) is the minimum number of leaves when no subtree may contain another; we obtain upper and lower bounds on l*(G). Leafage equals proper leafage on claw-free chordal graphs. We use asteroidal sets and structural properties of chordal graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1998, 18, 1; 23-48
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Clique graph representations of ptolemaic graphs
    Autorzy:
    McKee, Terry
    Powiązania:
    https://bibliotekanauki.pl/articles/744102.pdf
    Data publikacji:
    2010
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Ptolemaic graph
    clique graph
    chordal graph
    clique tree
    graph representation
    Opis:
    A graph is ptolemaic if and only if it is both chordal and distance-hereditary. Thus, a ptolemaic graph G has two kinds of intersection graph representations: one from being chordal, and the other from being distance-hereditary. The first of these, called a clique tree representation, is easily generated from the clique graph of G (the intersection graph of the maximal complete subgraphs of G). The second intersection graph representation can also be generated from the clique graph, as a very special case of the main result: The maximal Pₙ-free connected induced subgraphs of the p-clique graph of a ptolemaic graph G correspond in a natural way to the maximal $P_{n+1}$-free induced subgraphs of G in which every two nonadjacent vertices are connected by at least p internally disjoint paths.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2010, 30, 4; 651-661
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Requiring that Minimal Separators Induce Complete Multipartite Subgraphs
    Autorzy:
    McKee, Terry A.
    Powiązania:
    https://bibliotekanauki.pl/articles/31342426.pdf
    Data publikacji:
    2018-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    minimal separator
    complete multipartite graph
    chordal graph
    unichord-free graph
    Opis:
    Complete multipartite graphs range from complete graphs (with every partite set a singleton) to edgeless graphs (with a unique partite set). Requiring minimal separators to all induce one or the other of these extremes characterizes, respectively, the classical chordal graphs and the emergent unichord-free graphs. New theorems characterize several subclasses of the graphs whose minimal separators induce complete multipartite subgraphs, in particular the graphs that are 2-clique sums of complete, cycle, wheel, and octahedron graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 1; 263-273
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Edge cycle extendable graphs
    Autorzy:
    McKee, Terry
    Powiązania:
    https://bibliotekanauki.pl/articles/743340.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    cycle extendable graph
    chordal graph
    chordless graph
    minimally 2-connected graph
    Opis:
    A graph is edge cycle extendable if every cycle C that is formed from edges and one chord of a larger cycle C⁺ is also formed from edges and one chord of a cycle C' of length one greater than C with V(C') ⊆ V(C⁺). Edge cycle extendable graphs are characterized by every block being either chordal (every nontriangular cycle has a chord) or chordless (no nontriangular cycle has a chord); equivalently, every chord of a cycle of length five or more has a noncrossing chord.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 2; 373-378
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Efficient algorithms for minimal disjoint path problems on chordal graphs
    Autorzy:
    Gopalakrishnan, C.
    Satyan, C.
    Pandu Rangan, C.
    Powiązania:
    https://bibliotekanauki.pl/articles/972049.pdf
    Data publikacji:
    1995
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    chordal graph
    minimal paths
    disjoint paths
    clique
    bfs
    Opis:
    Disjoint paths have applications in establishing bottleneck-free communication between processors in a network. The problem of finding minimum delay disjoint paths in a network directly reduces to the problem of finding the minimal disjoint paths in the graph which models the network. Previous results for this problem on chordal graphs were an O(|V| |E|²) algorithm for 2 edge disjoint paths and an O(|V| |E|) algorithm for 2 vertex disjoint paths. In this paper, we give an O(|V| |E|) algorithm for 2 vertex disjoint paths and an O(|V|+|E|) algorithm for 2 edge disjoint paths, which is a significant improvement over the previous result.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1995, 15, 2; 119-145
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Complexity of Secure Domination Problem in Graphs
    Autorzy:
    Wang, Haichao
    Zhao, Yancai
    Deng, Yunping
    Powiązania:
    https://bibliotekanauki.pl/articles/31342335.pdf
    Data publikacji:
    2018-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    secure domination
    star convex bipartite graph
    doubly chordal graph
    NP-complete
    APX-complete
    Opis:
    A dominating set of a graph G is a subset D ⊆ V (G) such that every vertex not in D is adjacent to at least one vertex in D. A dominating set S of G is called a secure dominating set if each vertex u ∈ V (G) \ S has one neighbor v in S such that (S \ {v}) ∪ {u} is a dominating set of G. The secure domination problem is to determine a minimum secure dominating set of G. In this paper, we first show that the decision version of the secure domination problem is NP-complete for star convex bipartite graphs and doubly chordal graphs. We also prove that the secure domination problem cannot be approximated within a factor of (1−ε) ln |V | for any ε > 0, unless NP⊆DTIME (|V |O(log log |V|)). Finally, we show that the secure domination problem is APX-complete for bounded degree graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 2; 385-396
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Simplicial and nonsimplicial complete subgraphs
    Autorzy:
    McKee, Terry
    Powiązania:
    https://bibliotekanauki.pl/articles/743989.pdf
    Data publikacji:
    2011
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    simplicial clique
    strongly chordal graph
    trivially perfect graph
    hereditary clique-Helly graph
    strong p-Helly graph
    Opis:
    Define a complete subgraph Q to be simplicial in a graph G when Q is contained in exactly one maximal complete subgraph ('maxclique') of G; otherwise, Q is nonsimplicial. Several graph classes-including strong p-Helly graphs and strongly chordal graphs-are shown to have pairs of peculiarly related new characterizations: (i) for every k ≤ 2, a certain property holds for the complete subgraphs that are in k or more maxcliques of G, and (ii) in every induced subgraph H of G, that same property holds for the nonsimplicial complete subgraphs of H.
    One example: G is shown to be hereditary clique-Helly if and only if, for every k ≤ 2, every triangle whose edges are each in k or more maxcliques is itself in k or more maxcliques; equivalently, in every induced subgraph H of G, if each edge of a triangle is nonsimplicial in H, then the triangle itself is nonsimplicial in H.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2011, 31, 3; 577-586
    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