DSpace Repository :: Browsing by Subject "cycle"

Article

Open Access

Algebraic construction of a coboundary of a given cycle

(2007) Mazur, Marcin; Szybowski, Jacek

We present an algebraic construction of the coboundary of a given cycle as a simpler alternative to the geometric one introduced in [M. Allili, T. Kaczyński, <i>Geometric construction of a coboundary of a cycle</i>, Discrete Comput. Geom. 25 (2001), 125–140, T. Kaczyński, <i>Recursive coboundary formula for cycles in acyclic chain complexes</i>, Topol. Methods Nonlinear Anal. 18 (2001), 351–371].

Thesis

Restricted

Cykle i ścieżki w turniejach

(Data obrony: 2016-10-24) Szwed, Gabriela
Wydział Matematyki Stosowanej

Article

Open Access

Dominating sets and domination polynomials of certain graphs, II

(2010) Alikhani, Saeid; Peng, Yee Hock

The domination polynomial of a graph $G$ of order $n$ is the polynomial $D(G,x) = \sum _{i=\gamma(G)}^n d(G,i)x^i$, where $d(G,i)$ is the number of dominating sets of $G$ of size $i$, and $\gamma (G)$ is the domination number of $G$. In this paper, we obtain some properties of the coefficients of $D(G,x)$. Also, by study of the dominating sets and the domination polynomials of specific graphs denoted by $G^{\prime}(m)$, we obtain a relationship between the domination polynomial of graphs containing an induced path of length at least three, and the domination polynomial of related graphs obtained by replacing the path by shorter path. As examples of graphs $G^{\prime}(m)$, we study the dominating sets and domination polynomials of cycles and generalized theta graphs. Finally, we show that, if $n \equiv 0,2(mod\, 3)$ and $D(G,x) = D(C_n, x)$, then $G = C_n$.

Thesis

Restricted

Grafy $(H;k)$ stabilne

(Data obrony: 2011-07-29) Polańska, Karolina
Wydział Matematyki Stosowanej

Thesis

Restricted

Grafy $(H;k)$ stabilne

(Data obrony: 2011-07-29) Polańska, Karolina
Wydział Matematyki Stosowanej

Thesis

Restricted

Hipoteza Caccetty-Häggkvista

(Data obrony: 2018-10-18) Jamróz, Barbara
Wydział Matematyki Stosowanej

Thesis

Restricted

Hipoteza Erdősa-Sós

(Data obrony: 2009-10-15) Pieczka, Marcelina
Wydział Matematyki Stosowanej

Thesis

Restricted

O liczbie trójkątów w grafach bez $C_{5}$ i o liczbie $C_{5}$ w grafach bez trójkątów

(Data obrony: 2019-03-14) Gryz, Olga
Wydział Matematyki Stosowanej

Thesis

Restricted

O problemach wierzchołkowej stabilności w grafach

(Data obrony: 2012-09-27) Michałek, Natalia
Wydział Matematyki Stosowanej

Article

Open Access

On the crossing numbers of join products of W4+Pn and W4+Cn

(Wydawnictwa AGH, 2021) Staš, Michal; Valiska, Juraj

The crossing number $cr(G)$ of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. The main aim of the paper is to give the crossing number of the join product $W_{4}+P_{n}$ and $W_{4}+C_{n}$ for the wheel $W_4$ on five vertices, where $P_n$ and $C_n$ are the path and the cycle on $n$ vertices, respectively. Yue et al. conjectured that the crossing number of $W_{m}+C_{n}$ is equal to $Z(m+1)Z(n)+(Z(m)-1) \big \lfloor \frac{n}{2} \big \rfloor + n+ \big\lceil\frac{m}{2}\big\rceil +2$, for all $m,n \geq 3$, and where the Zarankiewicz's number $Z(n)=\big \lfloor \frac{n}{2} \big \rfloor \big \lfloor \frac{n-1}{2} \big \rfloor$ is defined for $n \geq 1$. Recently, this conjecture was proved for $W_{3}+C_{n}$ by Klešč. We establish the validity of this conjecture for $W_{4}+C_{n}$ and we also offer a new conjecture for the crossing number of the join product $W_{m}+P_{n}$ for $m \geq 3$ and $n \geq 2$.

Article

Open Access

On the structure of compact graphs

(Wydawnictwa AGH, 2017) Nikandish, Reza; Shaveisi, Farzad

A simple graph $G$ is called a compact graph if $G$ contains no isolated vertices and for each pair $x$, $y$ of non-adjacent vertices of $G$, there is a vertex z with $N(x)\cup N(y)\subseteq N(z)$, where $N(v)$ is the neighborhood of $v$, for every vertex $v$ of $G.$ In this paper, compact graphs with sufficient number of edges are studied. Also, it is proved that every regular compact graph is strongly regular. Some results about cycles in compact graphs are proved, too. Among other results, it is proved that if the ascending chain condition holds for the set of neighbors of a compact graph $G$, then the descending chain condition holds for the set of neighbors of $G$.

Thesis

Restricted

Podziały krawędziowe grafów gęstych

(Data obrony: 2018-07-16) Hubert, Maciej
Wydział Matematyki Stosowanej

Thesis

Restricted

Polepszenie warunków wystarczających na istnienie cyklu Hamiltona

(Data obrony: 2013-02-07) Pogodzińska, Anna
Wydział Matematyki Stosowanej

Article

Open Access

The crossing numbers of join products of four graphs of order five with paths and cycles

(Wydawnictwa AGH, 2023) Staš, Michal; Timková, Mária

The crossing number $\mathrm{cr}(G)$ of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. In the paper, we extend known results concerning crossing numbers of join products of four small graphs with paths and cycles. The crossing numbers of the join products $G^\ast + P_n$ and $G^\ast + C_n$ for the disconnected graph $G^\ast$ consisting of the complete tripartite graph $K_{1,1,2}$ and one isolated vertex are given, where $P_n$ and $C_n$ are the path and the cycle on $n$ vertices, respectively. In the paper also the crossing numbers of $H^{\ast}+P_{n}$ and $H^{\ast}+C_{n}$ are determined, where $H^{\ast}$ is isomorphic to the complete tripartite graph $K_{1,1,3}$. Finally, by adding new edges to the graphs $G^\ast$ and $H^\ast$, we are able to obtain crossing numbers of join products of two other graphs $G_1$ and $H_1$ with paths and cycles.