Temat: chordal graph - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: Maxclique and unit disk characterizations of strongly chordal graphs
Autorzy:: Caria, Pablo De
McKee, Terry A.
Tematy:: chordal graph
strongly chordal graph
clique
maxclique
closed neighborhood; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/30148683.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: Strongly pancyclic and dual-pancyclic graphs
Autorzy:: McKee, Terry
Tematy:: pancyclic graph
cycle extendable
chordal graph
pancyclic matroid
dual-chordal graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743097.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: The i-chords of cycles and paths
Autorzy:: McKee, Terry
Tematy:: chord
chordal graph
strongly chordal graph
ptolemaic graph
trivially perfect graph
threshold graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743264.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Strongly Unichord-Free Graphs
Autorzy:: McKee, Terry A.
Tematy:: unichord-free graph
strongly chordal graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31343449.pdf Link otwiera się w nowym oknie
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).
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: A New Characterization of Unichord-Free Graphs
Autorzy:: McKee, Terry A.
Tematy:: chordal graph
unichord-free graph
minimal separator; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31234070.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: The leafage of a chordal graph
Autorzy:: Lin, In-Jen
McKee, Terry
West, Douglas
Tematy:: chordal graph
subtree intersection representation
leafage; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/972051.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 7.

Tytuł:: Clique graph representations of ptolemaic graphs
Autorzy:: McKee, Terry
Tematy:: Ptolemaic graph
clique graph
chordal graph
clique tree
graph representation; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744102.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: Requiring that Minimal Separators Induce Complete Multipartite Subgraphs
Autorzy:: McKee, Terry A.
Tematy:: minimal separator
complete multipartite graph
chordal graph
unichord-free graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31342426.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 9.

Tytuł:: Efficient algorithms for minimal disjoint path problems on chordal graphs
Autorzy:: Gopalakrishnan, C.
Satyan, C.
Pandu Rangan, C.
Tematy:: chordal graph
minimal paths
disjoint paths
clique
bfs; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/972049.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 10.

Tytuł:: On-line graph coloring of $\mathbb{P}_{5}$-free graphs
Autorzy:: Cieślik, Iwona
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Artykuł

na półce

Informacja

Wyszukujesz frazę "chordal graph" wg kryterium: Temat