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: 6

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  cubic 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

On normal partitions in cubic graphs

100%
Fouquet J.-L., Vanherpe J.-M.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
293-312
EN
A normal partition of the edges of a cubic graph is a partition into trails (no repeated edge) such that each vertex is the end vertex of exactly one trail of the partition. We investigate this notion and give some results and problems.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On Fulkerson conjecture

100%
Fouquet J.-L., Vanherpe J.-M.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
253-272
EN
If G is a bridgeless cubic graph, Fulkerson conjectured that we can find 6 perfect matchings (a Fulkerson covering) with the property that every edge of G is contained in exactly two of them. A consequence of the Fulkerson conjecture would be that every bridgeless cubic graph has 3 perfect matchings with empty intersection (this problem is known as the Fan Raspaud Conjecture). A FR-triple is a set of 3 such perfect matchings. We show here how to derive a Fulkerson covering from two FR-triples. Moreover, we give a simple proof that the Fulkerson conjecture holds true for some classes of well known snarks.
3
Content available remote

Core Index of Perfect Matching Polytope for a 2-Connected Cubic Graph

70%
Wang X., Lin Y.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
189-201
EN
For a 2-connected cubic graph G, the perfect matching polytope P(G) of G contains a special point [...] xc=(13,13,…,13) $x^c = \left( {{1 \over 3},{1 \over 3}, \ldots ,{1 \over 3}} \right)$ . The core index ϕ(P(G)) of the polytope P(G) is the minimum number of vertices of P(G) whose convex hull contains xc. The Fulkerson’s conjecture asserts that every 2-connected cubic graph G has six perfect matchings such that each edge appears in exactly two of them, namely, there are six vertices of P(G) such that xc is the convex combination of them, which implies that ϕ(P(G)) ≤ 6. It turns out that the latter assertion in turn implies the Fan-Raspaud conjecture: In every 2-connected cubic graph G, there are three perfect matchings M1, M2, and M3 such that M1 ∩ M2 ∩ M3 = ∅. In this paper we prove the Fan-Raspaud conjecture for ϕ(P(G)) ≤ 12 with certain dimensional conditions.
4
Content available remote

The Fan-Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks

70%
Formanowicz P., Tanaś K.
International Journal of Applied Mathematics and Computer Science
|
2012
|
tom 22
|
nr 3
765-778
EN
It was conjectured by Fan and Raspaud (1994) that every bridgeless cubic graph contains three perfect matchings such that every edge belongs to at most two of them. We show a randomized algorithmic way of finding Fan-Raspaud colorings of a given cubic graph and, analyzing the computer results, we try to find and describe the Fan-Raspaud colorings for some selected classes of cubic graphs. The presented algorithms can then be applied to the pair assignment problem in cubic computer networks. Another possible application of the algorithms is that of being a tool for mathematicians working in the field of cubic graph theory, for discovering edge colorings with certain mathematical properties and formulating new conjectures related to the Fan-Raspaud conjecture.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some recent results on domination in graphs

61%
Plummer M.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 3
457-474
EN
In this paper, we survey some new results in four areas of domination in graphs, namely: (1) the toughness and matching structure of graphs having domination number 3 and which are "critical" in the sense that if one adds any missing edge, the domination number falls to 2; (2) the matching structure of graphs having domination number 3 and which are "critical" in the sense that if one deletes any vertex, the domination number falls to 2; (3) upper bounds on the domination number of cubic graphs; and (4) upper bounds on the domination number of graphs embedded in surfaces.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On a family of cubic graphs containing the flower snarks

61%
Fouquet J.-L., Thuillier H., Vanherpe J.-M.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 2
289-314
EN
We consider cubic graphs formed with k ≥ 2 disjoint claws $C_i ~ K_{1,3}$ (0 ≤ i ≤ k-1) such that for every integer i modulo k the three vertices of degree 1 of $C_i$ are joined to the three vertices of degree 1 of $C_{i-1}$ and joined to the three vertices of degree 1 of $C_{i+1}$. Denote by $t_i$ the vertex of degree 3 of $C_i$ and by T the set ${t₁,t₂,...,t_{k-1}}$. In such a way we construct three distinct graphs, namely FS(1,k), FS(2,k) and FS(3,k). The graph FS(j,k) (j ∈ {1,2,3}) is the graph where the set of vertices $⋃_{i = 0}^{i = k-1} V(C_i)∖T$ induce j cycles (note that the graphs FS(2,2p+1), p ≥ 2, are the flower snarks defined by Isaacs [8]). We determine the number of perfect matchings of every FS(j,k). A cubic graph G is said to be 2-factor hamiltonian if every 2-factor of G is a hamiltonian cycle. We characterize the graphs FS(j,k) that are 2-factor hamiltonian (note that FS(1,3) is the "Triplex Graph" of Robertson, Seymour and Thomas [15]). A strong matching M in a graph G is a matching M such that there is no edge of E(G) connecting any two edges of M. A cubic graph having a perfect matching union of two strong matchings is said to be a Jaeger's graph. We characterize the graphs FS(j,k) that are Jaeger's graphs.
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ć.