Temat: claw-free graphs - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: On the Erdős-Gyárfás conjecture in claw-free graphs
Autorzy:: Nowbandegani, Pouria Salehi
Esfandiari, Hossein
Haghighi, Mohammad Hassan Shirdareh
Bibak, Khodakhast
Tematy:: Erdős-Gyárfás conjecture
claw-free graphs
cycles; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/30148697.pdf Link otwiera się w nowym oknie
Opis:: The Erdős-Gyárfás conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of 2. Since this conjecture has proven to be far from reach, Hobbs asked if the Erdős-Gyárfás conjecture holds in claw-free graphs. In this paper, we obtain some results on this question, in particular for cubic claw-free graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: The flower conjecture in special classes of graphs
Autorzy:: Ryjáček, Zdeněk
Schiermeyer, Ingo
Tematy:: hamiltonian graphs
flower conjecture
square
claw-free graphs; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/972046.pdf Link otwiera się w nowym oknie
Opis:: We say that a spanning eulerian subgraph F ⊂ G is a flower in a graph G if there is a vertex u ∈ V(G) (called the center of F) such that all vertices of G except u are of the degree exactly 2 in F. A graph G has the flower property if every vertex of G is a center of a flower. Kaneko conjectured that G has the flower property if and only if G is hamiltonian. In the present paper we prove this conjecture in several special classes of graphs, among others in squares and in a certain subclass of claw-free graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs
Autorzy:: Seamone, Ben
Tematy:: Hamiltonian cycle
uniquely Hamiltonian graphs
claw-free graphs
triangle-free graphs; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31339495.pdf Link otwiera się w nowym oknie
Opis:: A graph is uniquely Hamiltonian if it contains exactly one Hamiltonian cycle. In this note, we prove that claw-free graphs with minimum degree at least 3 are not uniquely Hamiltonian. We also show that this is best possible by exhibiting uniquely Hamiltonian claw-free graphs with minimum degree 2 and arbitrary maximum degree. Finally, we show that a construction due to Entringer and Swart can be modified to construct triangle-free uniquely Hamiltonian graphs with minimum degree 3.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Semitotal domination in claw-free graphs
Autorzy:: Chen, Jie
Liang, Yi-Ping
Xu, Shou-Jun
Tematy:: semitotal domination
minimum degree
claw-free graphs; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59901342.pdf Link otwiera się w nowym oknie
Opis:: In an isolate-free graph $G$, a subset $S$ of vertices is a semitotal dominating set of $G$ if it is a dominating set of $G$ and every vertex in $S$ is within distance 2 of another vertex of $S$. The semitotal domination number of $G$, denoted by $\gamma_{t2}(G)$, is the minimum cardinality of a semitotal dominating set in $G$. We prove that if $G$ is a connected claw-free graph of order $n$ with minimum degree $\delta(G)\geq 2$ and is not one of fourteen exceptional graphs (ten of which are cycles), then $ \gamma_{t2}(G) \leq \tfrac{3}{7}n $, and we also characterize the graphs achieving equality, which are an infinite family of graphs. In particular, if we restrict $\delta(G) \geq 3$ and $G\ne K_4$, then we can improve the result to $ \gamma_{t2}(G) \leq \tfrac{2}{5}n $, solving the conjecture for the case of claw-free graphs, proposed by Goddard, Henning and McPillan in [Semitotal domination in graphs, Util. Math. 94 (2014) 67–81].
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: Vertex partitioning of graphs into odd induced subgraphs
Autorzy:: Aashtab, Arman
Akbari, Saieed
Ghanbari, Maryam
Shidani, Amitis
Tematy:: odd induced subgraph
subcubic graphs
claw-free graphs
line graphs
independent set; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59604071.pdf Link otwiera się w nowym oknie
Opis:: A graph $G$ is called an odd (even) graph if for every vertex $v\in V(G)$, $d_G(v)$ is odd (even). Let $G$ be a graph of even order. Scott in $1992$ proved that the vertices of every connected graph of even order can be partitioned into some odd induced forests. We denote the minimum number of odd induced subgraphs which partition $V(G)$ by $od(G)$. If all of the subgraphs are forests, then we denote it by $od_F(G)$. In this paper, we show that if $G$ is a connected subcubic graph of even order or $G$ is a connected planar graph of even order, then $od_F(G)\le 4$. Moreover, we show that for every tree $T$ of even order $od_F(T)\le 2$ and for every unicyclic graph $G$ of even order $od_F(G)\le 3$. Also, we prove that if $G$ is claw-free, then $V(G)$ can be partitioned into at most $\Delta(G)-1$ induced forests and possibly one independent set. Furthermore, we demonstrate that the vertex set of the line graph of a tree can be partitioned into at most two odd induced subgraphs and possibly one independent set.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: Total domination versus paired domination
Autorzy:: Schaudt, Oliver
Tematy:: total domination
upper total domination
paired domination
upper paired domination
generalized claw-free graphs; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743224.pdf Link otwiera się w nowym oknie
Opis:: A dominating set of a graph G is a vertex subset that any vertex of G either belongs to or is adjacent to. A total dominating set is a dominating set whose induced subgraph does not contain isolated vertices. The minimal size of a total dominating set, the total domination number, is denoted by γₜ. The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γₜ. A paired dominating set is a dominating set whose induced subgraph has a perfect matching. The minimal size of a paired dominating set, the paired domination number, is denoted by γₚ. The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Γₚ.
In this paper we prove several results on the ratio of these four parameters: For each r ≥ 2 we prove the sharp bound γₚ/γₜ ≤ 2 - 2/r for $K_{1,r}$-free graphs. As a consequence, we obtain the sharp bound γₚ/γₜ ≤ 2 - 2/(Δ+1), where Δ is the maximum degree. We also show for each r ≥ 2 that ${C₅,T_r}$-free graphs fulfill the sharp bound γₚ/γₜ ≤ 2 - 2/r, where $T_r$ is obtained from $K_{1,r}$ by subdividing each edge exactly once. We show that all of these bounds also hold for the ratio Γₚ/Γₜ. Further, we prove that a graph hereditarily has an induced paired dominating set if and only if γₚ ≤ Γₜ holds for any induced subgraph. We also give a finite forbidden subgraph characterization for this condition. We exactly determine the maximal value of the ratio γₚ/Γₜ taken over the induced subgraphs of a graph. As a consequence, we prove for each r ≥ 3 the sharp bound γₚ/Γₜ ≤ 2 - 2/r for graphs that do not contain the corona of $K_{1,r}$ as subgraph. In particular, we obtain the sharp bound γₚ/Γₜ ≤ 2 - 2/Δ.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 7.

Tytuł:: Some Observations on the Smallest Adjacency Eigenvalue of a Graph
Autorzy:: Cioabă, Sebastian M.
Elzinga, Randall J.
Gregory, David A.
Tematy:: graph spectrum
smallest eigenvalue
adjacency matrix
graph decomposition
clique partition
claw-free graphs
maximum cut; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31548045.pdf Link otwiera się w nowym oknie
Opis:: In this paper, we discuss various connections between the smallest eigenvalue of the adjacency matrix of a graph and its structure. There are several techniques for obtaining upper bounds on the smallest eigenvalue, and some of them are based on Rayleigh quotients, Cauchy interlacing using induced subgraphs, and Haemers interlacing with vertex partitions and quotient matrices. In this paper, we are interested in obtaining lower bounds for the smallest eigenvalue. Motivated by results on line graphs and generalized line graphs, we show how graph decompositions can be used to obtain such lower bounds.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: On $s$-hamiltonian-connected line graphs
Autorzy:: Ma, Xiaoling
Lai, Hong-Jian
Zhan, Mingquan
Zhang, Taoye
Zhou, Ju
Tematy:: line graph
claw-free graph
$s$-hamiltonian-connected
collapsible graphs
reductions; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59882195.pdf Link otwiera się w nowym oknie
Opis:: For an integer $s\ge 0$, $G$ is $s$-hamiltonian-connected if for any vertex subset $S\subseteq V(G)$ with $|S|\le s$, $G-S$ is hamiltonian-connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see [Reflections on graph theory, J. Graph Theory 10 (1986) 309–324]), and Kužel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian-connected (see [Z. Ryjáček and P. Vrána, Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs, J. Graph Theory 66 (2011) 152–173]). In this paper we prove the following. (i) For $s\ge 3$, every $(s+4)$-connected line graph is $s$-hamiltonian-connected. (ii) For $s\ge 0$, every $(s+4)$-connected line graph of a claw-free graph is $s$-hamiltonian-connected.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "claw-free graphs" wg kryterium: Temat