Temat: 4-connected graph - Prolib Integro

Skocz do pozycji: 1.

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
Tematy:: 4-connected graph
removable edge
fragment
atom; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32083895.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: Distribution of Contractible Edges and the Structure of Noncontractible Edges having Endvertices with Large Degree in a 4-Connected Graph
Autorzy:: Nakamura, Shunsuke
Tematy:: 4-connected graph
contractible edge
cross free; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32323873.pdf Link otwiera się w nowym oknie
Opis:: Let G be a 4-connected graph G, and let E_c(G) denote the set of 4-contractible edges of G. We prove results concerning the distribution of edges in E_c(G). Roughly speaking, we show that there exists a set K₀ and a mapping φ : K₀ → E_c(G) such that |φ^-1(e)| ≤ 4 for each e ∈ E_c(G).
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: A New Proof that 4-Connected Planar Graphs are Hamiltonian-Connected
Autorzy:: Lu, Xiaoyun
West, Douglas B.
Tematy:: 4-connected planar graph
Hamiltonian-connected
Tutte-path; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31340879.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Longer Cycles in Essentially 4-Connected Planar Graphs
Autorzy:: Fabrici, Igor
Harant, Jochen
Mohr, Samuel
Schmidt, Jens M.
Tematy:: essentially 4-connected planar graph
longest cycle
circumference
shortness coefficient; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32083770.pdf Link otwiera się w nowym oknie
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) $.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: Internally 4-Connected Graphs with No {Cube, V₈}-Minor
Autorzy:: Lewchalermvongs, Chanun
Ananchuen, Nawarat
Tematy:: internally 4-connected
minor
cube graph
V₈ graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32083888.pdf Link otwiera się w nowym oknie
Opis:: A simple graph is a minor of another if the first is obtained from the second by deleting vertices, deleting edges, contracting edges, and deleting loops and parallel edges that are created when we contract edges. A cube is an internally 4-connected planar graph with eight vertices and twelve edges corresponding to the skeleton of the cube in the platonic solid, and the Wagner graph V₈ is an internally 4-connected nonplanar graph obtained from a cube by introducing a twist. A complete characterization of all internally 4-connected graphs with no V₈ minor is given in J. Maharry and N. Robertson, The structure of graphs not topologically containing the Wagner graph, J. Combin. Theory Ser. B 121 (2016) 398–420; on the other hand, only a characterization of 3-connected graphs with no cube minor is given in J. Maharry, A characterization of graphs with no cube minor, J. Combin. Theory Ser. B 80 (2008) 179–201. In this paper we determine all internally 4-connected graphs that contain neither cube nor V₈ as minors. This result provides a step closer to a complete characterization of all internally 4-connected graphs with no cube minor.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: A characterization of internally 4-connected $\{P_{10}− \{v_1,v_2\}\}$-minor-free graphs
Autorzy:: Zhou, Xiaomin
Yang, Weihua
Guan, Xiaxia
Qin, Chengfu
Tematy:: internally $4$-connected
$V_{8}^{--}$-minor-free
Petersen graph
$2$-con\-nected minor; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59898556.pdf Link otwiera się w nowym oknie
Opis:: Let $P_{10}$ be the Petersen graph. Let $V_{8}^{--} =P_{10}-\{v_{1}, v_{2}\}$, where $v_{1}$ and $v_{2}$ are the adjacent vertices of $P_{10}$. In this paper, all internally $4$-connected graphs that do not contain $V_{8}^{--}$ as a minor are charaterized.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "4-connected graph" wg kryterium: Temat