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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 20
Tytuł:
On normal partitions in cubic graphs
Autorzy:
Fouquet, Jean-Luc
Vanherpe, Jean-Marie
Powiązania:
https://bibliotekanauki.pl/articles/743177.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cubic graph
edge-partition
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 2; 293-312
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Fulkerson conjecture
Autorzy:
Fouquet, Jean-Luc
Vanherpe, Jean-Marie
Powiązania:
https://bibliotekanauki.pl/articles/743867.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cubic graph
perfect matchings
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 2; 253-272
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Hamiltonian Cycles in Claw-Free Cubic Graphs
Autorzy:
Mohr, Elena
Rautenbach, Dieter
Powiązania:
https://bibliotekanauki.pl/articles/32361735.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian cycle
claw-free graph
cubic graph
Opis:
We show that every claw-free cubic graph of order $n$ at least 8 has at most $ 2\floor{ \frac{n}{4} } $ Hamiltonian cycles, and we also characterize all extremal graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 309-313
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Mácajová and Škoviera conjecture on cubic graphs
Autorzy:
Fouquet, Jean-Luc
Vanherpe, Jean-Marie
Powiązania:
https://bibliotekanauki.pl/articles/744280.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Cubic graph
edge-partition
traceable graphs
Opis:
A conjecture of Mácajová and Skoviera asserts that every bridgeless cubic graph has two perfect matchings whose intersection does not contain any odd edge cut. We prove this conjecture for graphs with few vertices and we give a stronger result for traceable graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 2; 315-333
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Some recent results on domination in graphs
Autorzy:
Plummer, Michael
Powiązania:
https://bibliotekanauki.pl/articles/743609.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
matching
toughness
cubic graph
triangulation
genus
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 3; 457-474
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On 2-rainbow domination number of functigraph and its complement
Autorzy:
Shaminezhad, Athena
Vatandoost, Ebrahim
Powiązania:
https://bibliotekanauki.pl/articles/255140.pdf
Data publikacji:
2020
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
2-rainbow domination number
functigraph
complement
cubic graph
Opis:
Let G be a graph and ƒ : V(G) → P({1, 2}) be a function where for every vertex v ∈ V(G), with ƒ (v) = ∅ we have [formula]. Then ƒ is a 2-rainbow dominating function or a 2RDF of G. The weight of ƒ is[formula]. The minimum weight of all 2-rainbow dominating functions is 2-rainbow domination number of G, denoted by [formula]. Let G 1 and G2 be two copies of a graph G with disjoint vertex sets V(G 1) and V(G2), and let σ be a function from V(G 1) to V(G2). We define the functigraph C(G,σ) to be the graph that has the vertex set V(C(G, ,σ)) = V(G 1) U V(G2), and the edge set [formula]. In this paper, 2-rainbow domination number of the functigraph of C(G, ,σ) and its complement are investigated. We obtain a general bound for [formula] and we show that this bound is sharp.
Źródło:
Opuscula Mathematica; 2020, 40, 5; 617-627
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On odd and semi-odd linear partitions of cubic graphs
Autorzy:
Fouquet, Jean-Luc
Thuillier, Henri
Vanherpe, Jean-Marie
Wojda, Adam
Powiązania:
https://bibliotekanauki.pl/articles/743181.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Cubic graph
linear arboricity
strong matching
edge-colouring
Opis:
A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition.
In this paper we consider linear partitions of cubic simple graphs for which it is well known that la(G) = 2. A linear partition $L = (L_B,L_R)$ is said to be odd whenever each path of $L_B ∪ L_R$ has odd length and semi-odd whenever each path of $L_B$ (or each path of $L_R$) has odd length.
In [2] Aldred and Wormald showed that a cubic graph G is 3-edge colourable if and only if G has an odd linear partition. We give here more precise results and we study moreover relationships between semi-odd linear partitions and perfect matchings.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 2; 275-292
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Critical and Flow-Critical Snarks Coincide
Autorzy:
Máčajová, Edita
Škoviera, Martin
Powiązania:
https://bibliotekanauki.pl/articles/32083890.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
nowhere-zero flow
edge-colouring
cubic graph
snark
Opis:
Over the past twenty years, critical and bicritical snarks have been appearing in the literature in various forms and in different contexts. Two main variants of criticality of snarks have been studied: criticality with respect to the non-existence of a 3-edge-colouring and criticality with respect to the non-existence of a nowhere-zero 4-flow. In this paper we show that these two kinds of criticality coincide, thereby completing previous partial results of de Freitas et al. [Electron. Notes Discrete Math. 50 (2015) 199–204] and Fiol et al. [Electron. J. Combin. 25 (2017) #P4.54].
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 503-511
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
Autorzy:
Furmańczyk, H.
Kubale, M.
Powiązania:
https://bibliotekanauki.pl/articles/230004.pdf
Data publikacji:
2015
Wydawca:
Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:
batch scheduling
equitable coloring
semi-equitable coloring
cubic graph
Opis:
In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP-complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize the makespan.
Źródło:
Archives of Control Sciences; 2015, 25, 1; 109-116
1230-2384
Pojawia się w:
Archives of Control Sciences
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A conjecture on the prevalence of cubic bridge graphs
Autorzy:
Filar, Jerzy
Haythorpe, Michael
Nguyen, Giang
Powiązania:
https://bibliotekanauki.pl/articles/744564.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian graph
non-Hamiltonian graph
cubic bridge graph
Opis:
Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 1; 175-179
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Dominating Vertex Covers: The Vertex-Edge Domination Problem
Autorzy:
Klostermeyer, William F.
Messinger, Margaret-Ellen
Yeo, Anders
Powiązania:
https://bibliotekanauki.pl/articles/32083812.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cubic graph
dominating set
vertex cover
vertex-edge dominating set
Opis:
The vertex-edge domination number of a graph, γve(G), is defined to be the cardinality of a smallest set D such that there exists a vertex cover C of G such that each vertex in C is dominated by a vertex in D. This is motivated by the problem of determining how many guards are needed in a graph so that a searchlight can be shone down each edge by a guard either incident to that edge or at most distance one from a vertex incident to the edge. Our main result is that for any cubic graph G with n vertices, γve(G) ≤ 9n/26. We also show that it is NP-hard to decide if γve(G) = γ(G) for bipartite graph G.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 123-132
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Coverings of Cubic Graphs and 3-Edge Colorability
Autorzy:
Plachta, Leonid
Powiązania:
https://bibliotekanauki.pl/articles/32083839.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
uncolorable cubic graph
covering of graphs
voltage permutation graph
resistance
nowhere-zero 4-flow
Opis:
Let \(h:\tilde{G}→G\) be a finite covering of 2-connected cubic (multi)graphs where G is 3-edge uncolorable. In this paper, we describe conditions under which \(\tilde{G}\) is 3-edge uncolorable. As particular cases, we have constructed regular and irregular 5-fold coverings \(f:\tilde{G}→G\) of uncolorable cyclically 4-edge connected cubic graphs and an irregular 5-fold covering \(g:\tilde{H}→H\) of uncolorable cyclically 6-edge connected cubic graphs. In [13], Steffen introduced the resistance of a subcubic graph, a characteristic that measures how far is this graph from being 3-edge colorable. In this paper, we also study the relation between the resistance of the base cubic graph and the covering cubic graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 311-334
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On a family of cubic graphs containing the flower snarks
Autorzy:
Fouquet, Jean-Luc
Thuillier, Henri
Vanherpe, Jean-Marie
Powiązania:
https://bibliotekanauki.pl/articles/744266.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cubic graph
perfect matching
strong matching
counting
hamiltonian cycle
2-factor hamiltonian
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 2; 289-314
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Core Index of Perfect Matching Polytope for a 2-Connected Cubic Graph
Autorzy:
Wang, Xiumei
Lin, Yixun
Powiązania:
https://bibliotekanauki.pl/articles/31343794.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Fulkerson’s conjecture
Fan-Raspaud conjecture
cubic graph
perfect matching polytope
core index
Opis:
For a 2-connected cubic graph $G$, the perfect matching polytope $P(G)$ of $G$ contains a special point \( x^c = ( \tfrac{1}{3},\tfrac{1}{3},…,\tfrac{1}{3}) \). The core index $ \phi(P(G)) $ of the polytope $P(G)$ is the minimum number of vertices of $P(G)$ whose convex hull contains $ x^c$. 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 $ x^c $ is the convex combination of them, which implies that $ \phi(P(G)) \le 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 $M_1$, $M_2$, and $M_3$ such that $M_1 \cap M_2 \cap M_3 = \emptyset $. In this paper we prove the Fan-Raspaud conjecture for $ \phi(P(G)) \le 12 $ with certain dimensional conditions.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 189-201
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Decompositions of Cubic Traceable Graphs
Autorzy:
Liu, Wenzhong
Li, Panpan
Powiązania:
https://bibliotekanauki.pl/articles/31867897.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
decomposition
cubic traceable graph
spanning tree
matching
2-regular graph
Opis:
A traceable graph is a graph with a Hamilton path. The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular graph and a matching. We prove the conjecture for cubic traceable graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 35-49
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 20

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