Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 9

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  chordal graph
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The leafage of a chordal graph

100%
Lin I.-J., McKee T., West D.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 1
23-48
EN
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.
2
Content available remote

Requiring that Minimal Separators Induce Complete Multipartite Subgraphs

100%
McKee T. A.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
263-273
EN
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.
3
Content available remote

A New Characterization of Unichord-Free Graphs

100%
McKee T. A.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
765-771
EN
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.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Edge cycle extendable graphs

100%
McKee T.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 2
373-378
EN
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.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Efficient algorithms for minimal disjoint path problems on chordal graphs

88%
Gopalakrishnan C., Satyan C., Pandu Rangan C.
Discussiones Mathematicae Graph Theory
|
1995
|
tom 15
|
nr 2
119-145
EN
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.
6
Content available remote

Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs

88%
Caria P. D., McKee T. A.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
593-602
EN
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
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Strongly pancyclic and dual-pancyclic graphs

88%
McKee T.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 1
5-14
EN
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.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Clique graph representations of ptolemaic graphs

88%
McKee T.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 4
651-661
EN
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.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The i-chords of cycles and paths

75%
McKee T.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 4
607-615
EN
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.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.