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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 24
Tytuł:
Edge-Connectivity and Edges of Even Factors of Graphs
Autorzy:
Haghparast, Nastaran
Kiani, Dariush
Powiązania:
https://bibliotekanauki.pl/articles/31343450.pdf
Data publikacji:
2019-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
3-edge-connected graph
2-edge-connected graph
even factor
component
Opis:
An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Jackson and Yoshimoto showed that if G is a 3-edge-connected graph with |G| ≥ 5 and v is a vertex with degree 3, then G has an even factor F containing two given edges incident with v in which each component has order at least 5. We prove that this theorem is satisfied for each pair of adjacent edges. Also, we show that each 3-edge-connected graph has an even factor F containing two given edges e and f such that every component containing neither e nor f has order at least 5. But we construct infinitely many 3-edge-connected graphs that do not have an even factor F containing two arbitrary prescribed edges in which each component has order at least 5.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 2; 357-364
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Large Contractible Subgraphs of a 3-Connected Graph
Autorzy:
Karpov, Dmitri V.
Powiązania:
https://bibliotekanauki.pl/articles/32083775.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
connectivity
3-connected graph
contractible subgraph
Opis:
Let m ≥ 5 be a positive integer and let G be a 3-connected graph on at least 2m + 1 vertices. We prove that G has a contractible set W such that m ≤ |W| ≤ 2m − 4. (Recall that a set W ⊂ V (G) of a 3-connected graph G is contractible if the graph G(W) is connected and the graph G − W is 2-connected.) A particular case for m = 4 is that any 3-connected graph on at least 11 vertices has a contractible set of 5 or 6 vertices.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 83-101
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Distribution of Contractible Edges and the Structure of Noncontractible Edges having Endvertices with Large Degree in a 4-Connected Graph
Autorzy:
Nakamura, Shunsuke
Powiązania:
https://bibliotekanauki.pl/articles/32323873.pdf
Data publikacji:
2021-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
4-connected graph
contractible edge
cross free
Opis:
Let G be a 4-connected graph G, and let Ec(G) denote the set of 4-contractible edges of G. We prove results concerning the distribution of edges in Ec(G). Roughly speaking, we show that there exists a set K0 and a mapping φ : K0 → Ec(G) such that |φ-1(e)| ≤ 4 for each e ∈ Ec(G).
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1051-1066
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs
Autorzy:
Zheng, Wei
Broersma, Hajo
Wang, Ligong
Powiązania:
https://bibliotekanauki.pl/articles/32361744.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
toughness
forbidden subgraph
Hamilton-connected graph
Hamiltonicity
Opis:
A graph G is called Hamilton-connected if for every pair of distinct vertices {u, v} of G there exists a Hamilton path in G that connects u and v. A graph G is said to be t-tough if t·ω(G − X) ≤ |X| for all X ⊆ V (G) with ω(G − X) > 1. The toughness of G, denoted τ (G), is the maximum value of t such that G is t-tough (taking τ (Kn) = ∞ for all n ≥ 1). It is known that a Hamilton-connected graph G has toughness τ (G) > 1, but that the reverse statement does not hold in general. In this paper, we investigate all possible forbidden subgraphs H such that every H-free graph G with τ (G) > 1 is Hamilton-connected. We find that the results are completely analogous to the Hamiltonian case: every graph H such that any 1-tough H-free graph is Hamiltonian also ensures that every H-free graph with toughness larger than one is Hamilton-connected. And similarly, there is no other forbidden subgraph having this property, except possibly for the graph K1 ∪ P4 itself. We leave this as an open case.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 187-196
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Removable Edges on a Hamilton Cycle or Outside a Cycle in a 4-Connected Graph
Autorzy:
Wu, Jichang
Broersma, Hajo
Mao, Yaping
Ma, Qin
Powiązania:
https://bibliotekanauki.pl/articles/32083895.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
4-connected graph
removable edge
fragment
atom
Opis:
Let G be a 4-connected graph. We call an edge e of G removable if the following sequence of operations results in a 4-connected graph: delete e from G; if there are vertices with degree 3 in G−e, then for each (of the at most two) such vertex x, delete x from G − e and turn the three neighbors of x into a clique by adding any missing edges (avoiding multiple edges). In this paper, we continue the study on the distribution of removable edges in a 4-connected graph G, in particular outside a cycle of G or in a spanning tree or on a Hamilton cycle of G. We give examples to show that our results are in some sense best possible.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 559-587
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Research problems from the 18th Workshop '3in1' 2009
Autorzy:
Meszka, M. [ed.]
Powiązania:
https://bibliotekanauki.pl/articles/255619.pdf
Data publikacji:
2010
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
Hamilton-connected graph
hamiltonian graph
dominating cycle
bihomogeneously traceble graph
Opis:
A collection of open problems that were posed at the 18th Workshop '3in1', held on November 26-28, 2009 in Krakow, Poland. The problems are presented by Zdenek Ryjacek in "Does the Thomassen's conjecture imply N=NP?" and "Dominating cycles and hamiltonian prisms", and by Carol T. Zamfirescu in "Two problems on bihomogeneously traceable digraphs".
Źródło:
Opuscula Mathematica; 2010, 30, 4; 527-532
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
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ł:
Rainbow Connection In Sparse Graphs
Autorzy:
Kemnitz, Arnfried
Przybyło, Jakub
Schiermeyer, Ingo
Woźniak, Mariusz
Powiązania:
https://bibliotekanauki.pl/articles/30146690.pdf
Data publikacji:
2013-03-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow-connected graph
rainbow colouring
rainbow connection number
Opis:
An edge-coloured connected graph $G = (V,E)$ is called rainbow-connected if each pair of distinct vertices of $G$ is connected by a path whose edges have distinct colours. The rainbow connection number of $G$, denoted by $ \text{rc}(G)$, is the minimum number of colours such that $G$ is rainbow-connected. In this paper we prove that $ \text{rc}(G) \le k $ if $ |V (G)| = n $ and \( |E(G)| \ge \binom{n-k+1}{2} + k -1 \) for all integers $n$ and $k$ with $n − 6 \le k \le n − 3 $. We also show that this bound is tight.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 181-192
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Restricted Size Ramsey Number Involving a Path P3
Autorzy:
Silaban, Denny Riama
Baskoro, Edy Tri
Uttunggadewa, Saladin
Powiązania:
https://bibliotekanauki.pl/articles/31343288.pdf
Data publikacji:
2019-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
restricted size Ramsey number
path
connected graph
star
Opis:
For any pair of graphs $G$ and $H$, both the size Ramsey number $ \hat{r}(G,H) $ and the restricted size Ramsey number $ r^\ast (G,H) $ are bounded above by the size of the complete graph with order equals to the Ramsey number $ r(G,H) $, and bounded below by $ e(G) + e(H) − 1 $. Moreover, trivially,$ \hat{r} (G,H) \le r^\ast (G,H) $. When introducing the size Ramsey number for graph, Erdős et al. (1978) asked two questions; (1) Do there exist graphs $G$ and $H$ such that $ \hat{r} (G,H) $ attains the upper bound? and (2) Do there exist graphs $G$ and $H$ such that $ \hat{r} (G,H) $ is significantly less than the upper bound? In this paper we consider the restricted size Ramsey number $ r^\ast (G,H) $. We answer both questions above for $ r^\ast (G,H) $ when $ G = P_3 $ and $H$ is a connected graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 757-769
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Perfect connected-dominant graphs
Autorzy:
Zverovich, Igor
Powiązania:
https://bibliotekanauki.pl/articles/743393.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Connected domination
perfect connected-dominant graph
Opis:
If D is a dominating set and the induced subgraph G(D) is connected, then D is a connected dominating set. The minimum size of a connected dominating set in G is called connected domination number $γ_c(G)$ of G. A graph G is called a perfect connected-dominant graph if $γ(H) = γ_c(H)$ for each connected induced subgraph H of G.We prove that a graph is a perfect connected-dominant graph if and only if it contains no induced path P₅ and induced cycle C₅.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 1; 159-162
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Sufficient Condition for Graphs to Be Super k-Restricted Edge Connected
Autorzy:
Wang, Shiying
Wang, Meiyu
Zhang, Lei
Powiązania:
https://bibliotekanauki.pl/articles/31341790.pdf
Data publikacji:
2017-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
neighborhood
k -restricted edge connectivity
super k -restricted edge connected graph
Opis:
For a subset $S$ of edges in a connected graph $G$, $S$ is a $k$-restricted edge cut if $G − S$ is disconnected and every component of $G − S$ has at least $k$ vertices. The $k$-restricted edge connectivity of $G$, denoted by $ \lambda_k (G) $, is defined as the cardinality of a minimum $k$-restricted edge cut. Let \( \xi_k(G) = \text{min} \{ | [ X , \overline{X} ] | : |X| = k, G[X] \) is connected $ \} $, where $ \overline{X} = V (G) \backslash X $. A graph $G$ is super $k$-restricted edge connected if every minimum $k$-restricted edge cut of $G$ isolates a component of order exactly $k$. Let $k$ be a positive integer and let $G$ be a graph of order $ \nu \ge 2k$. In this paper, we show that if $ | N( u ) \cup N( v ) | \ge k +1 $ for all pairs $u$, $v$ of nonadjacent vertices and $ \xi_k (G) \le \floor{ ν/2}+k $, then $G$ is super $k$-restricted edge connected.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 537-545
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Conflict-Free Connections of Graphs
Autorzy:
Czap, Július
Jendroľ, Stanislav
Valiska, Juraj
Powiązania:
https://bibliotekanauki.pl/articles/31342254.pdf
Data publikacji:
2018-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
conflict-free connection
2-edge-connected graph
tree
Opis:
An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path, which contains a color used on exactly one of its edges. In this paper the question for the smallest number of colors needed for a coloring of edges of G in order to make it conflict-free connected is investigated. We show that the answer is easy for 2-edge-connected graphs and very difficult for other connected graphs, including trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 911-920
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Conflict-Free Vertex-Connections of Graphs
Autorzy:
Li, Xueliang
Zhang, Yingying
Zhu, Xiaoyu
Mao, Yaping
Zhao, Haixing
Jendrol’, Stanislav
Powiązania:
https://bibliotekanauki.pl/articles/31868621.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
vertex-coloring
conflict-free vertex-connection
2-connected graph
tree
Opis:
A path in a vertex-colored graph is called conflict-free if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be conflict-free vertex-connected if any two vertices of the graph are connected by a conflict-free path. This paper investigates the question: for a connected graph G, what is the smallest number of colors needed in a vertex-coloring of G in order to make G conflict-free vertex-connected. As a result, we get that the answer is easy for 2-connected graphs, and very difficult for connected graphs with more cut-vertices, including trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 51-65
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A New Proof that 4-Connected Planar Graphs are Hamiltonian-Connected
Autorzy:
Lu, Xiaoyun
West, Douglas B.
Powiązania:
https://bibliotekanauki.pl/articles/31340879.pdf
Data publikacji:
2016-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
4-connected planar graph
Hamiltonian-connected
Tutte-path
Opis:
We prove a theorem guaranteeing special paths of faces in 2-connected plane graphs. As a corollary, we obtain a new proof of Thomassen’s theorem that every 4-connected planar graph is Hamiltonian-connected.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 3; 555-564
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Longer Cycles in Essentially 4-Connected Planar Graphs
Autorzy:
Fabrici, Igor
Harant, Jochen
Mohr, Samuel
Schmidt, Jens M.
Powiązania:
https://bibliotekanauki.pl/articles/32083770.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
essentially 4-connected planar graph
longest cycle
circumference
shortness coefficient
Opis:
A planar 3-connected graph $G$ is called essentially 4-connected if, for every 3-separator $S$, at least one of the two components of $G − S$ is an isolated vertex. Jackson and Wormald proved that the length $ \text{circ} (G) $ of a longest cycle of any essentially 4-connected planar graph $G$ on n vertices is at least $ \frac{ 2n+4 }{5} $ and Fabrici, Harant and Jendrol’ improved this result to $ \text{circ} (G) \ge 1/2 (n+4) $. In the present paper, we prove that an essentially 4-connected planar graph on $n$ vertices contains a cycle of length at least $ 3/5 (n+2) $ and that such a cycle can be found in time $ O(n^2) $.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 269-277
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 24

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