DSpace Repository :: Browsing by Subject "bipartite graph"

Article

Open Access

2-biplacement without fixed points of (p,q)-bipartite graphs

(2005) Orchel, Beata

In this paper we consider 2-biplacement without fixed points of paths and $(p, q)$-bipartite graphs of small size. We give all $(p, q)$-bipartite graphs $G$ of size q for which the set $\mathcal{S}^{*}(G)$ of all 2-biplacements of $G$ without fixed points is empty.

Article

Open Access

3-biplacement of bipartite graphs

(2008) Adamus, Lech; Leśniak, Edyta; Orchel, Beata

Let $G=(L,R;E)$ be a bipartite graph with color classes $L$ and $R$ and edge set $E$. A set of two bijections $\{\varphi_1 , \varphi_2\}$, $\varphi_1 , \varphi_2 :L \cup R \to L \cup R$, is said to be a $3$-biplacement of $G$ if $\varphi_1(L)= \varphi_2(L) = L$ and $E \cap \varphi_1^*(E)=\emptyset$, $E \cap \varphi_2^*(E)=\emptyset$, $\varphi_1^*(E) \cap \varphi_2^*(E)=\emptyset$, where$\varphi_1^*$, $\varphi_2^*$ are the maps defined on $E$, induced by $\varphi_1$, $\varphi_2$, respectively. We prove that if $|L|=p$, $|R|=q$, $3 \leq p \leq q$, then every graph $G=(L,R;E)$ of size at most $p$ has a $3$-biplacement.

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

Hamiltonowskość grafu - nowe spojrzenie na klasyczne warunki wystarczające

(Data obrony: 2012-06-26) Iwaniec, Judyta
Wydział Matematyki Stosowanej

Article

Open Access

Independent set dominating sets in bipartite graphs

(2005) Zelinka, Bohdan

The paper continues the study of independent set dominating sets in graphs which was started by E. Sampathkumar. A subset $D$ of the vertex set $V(G)$ of a graph $G$ is called a set dominating set (shortly sd-set) in $G$, if for each set $X \subseteq V(G)-D$ there exists a set $Y \subseteq D$ such that the subgraph $X \cup Y$ of $G$ induced by $\langle X \cup Y\rangle$ is connected. The minimum number of vertices of an sd-set in $G$ is called the set domination number $\gamma_s(G)$ of $G$. An sd-set $D$ in $G$ such that $|D|=\gamma_s(G)$ is called a $\gamma_s$-set in $G$. In this paper we study sd-sets in bipartite graphs which are simultaneously independent. We apply the theory of hypergraphs.

Thesis

Restricted

Krawędzie nietrasowalne w grafach dwudzielnych prawie zrównoważonych

(Data obrony: 2018-04-24) Pawłowski, Kamil
Wydział Matematyki Stosowanej

Thesis

Restricted

Krawędzie nietrasowalne w grafach trasowalnych

(Data obrony: 2012-12-03) Rapacz, Mateusz
Wydział Matematyki Stosowanej

Article

Open Access

Minimum k-critical-bipartite graphs: the irregular case

(Wydawnictwa AGH, 2026) Cichacz-Przeniosło, Sylwia; Görlich, Agnieszka; Suchan, Karol

We study the problem of finding a minimum $k$-critical-bipartite graph of order $(n,m)$: a bipartite graph $G=(U,V;E)$, with $|U|=n$, $|V|=m$, and $n\gt m\gt 1$, which is $k$-critical-bipartite, and the tuple $(|E|, \Delta_U, \Delta_V)$, where $\Delta_U$ and $\Delta_V$ denote the maximum degree in $U$ and $V$, respectively, is lexicographically minimum over all such graphs. $G$ is $k$-critical-bipartite if deleting any set of at most $k=n-m$ vertices from $U$ yields $G'$ that has a complete matching, i.e., a matching of size $m$. Cichacz and Suchan solved the problem for biregular bipartite graphs. Here, we extend their results to bipartite graphs that are not biregular. We prove tight lower bounds on the connectivity of $k$-critical-bipartite graphs, and we show that $k$-critical-bipartite graphs are expander graphs.

Article

Open Access

Notes on topological indices of graph and its complement

(2013) Madaras, Tomáš; Mockovčiaková, Martina

In this note, we derive the lower bound on the sum for Wiener index of bipartite graph and its bipartite complement, as well as the lower and upper bounds on this sum for the Randić index and Zagreb indices. We also discuss the quality of these bounds.

Thesis

Restricted

O skojarzeniach w grafach

(Data obrony: 2011-07-07) Żupnik, Magdalena; Uzar, Jakub; Widuch, Justyna
Wydział Matematyki Stosowanej

Thesis

Restricted

O skojarzeniach w grafach

(Data obrony: 2011-07-07) Widuch, Justyna; Uzar, Jakub; Żupnik, Magdalena
Wydział Matematyki Stosowanej

Thesis

Restricted

O skojarzeniach w grafach

(Data obrony: 2011-07-07) Uzar, Jakub; Widuch, Justyna; Żupnik, Magdalena
Wydział Matematyki Stosowanej

Article

Open Access

Open trails in digraphs

(2011) Cichacz-Przeniosło, Sylwia; Görlich, Agnieszka

It has been shown in [S. Cichacz, A. Görlich, Decomposition of complete bipartite graphs into open trails, Preprint MD 022, (2006)] that any bipartite graph $K_{a,b}$, is decomposable into open trails of prescribed even lengths. In this article we consider the corresponding question for directed graphs. We show that the complete directed graphs $\overleftrightarrow{K}_n$ and $\overleftrightarrow{K}_{a,b}$ are arbitrarily decomposable into directed open trails.

Thesis

Restricted

Podział grafów dwudzielnych na cykle niezależne

(Data obrony: 2016-07-12) Daniek, Katarzyna
Wydział Matematyki Stosowanej

Article

Open Access

Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments

(AGH University of Science and Technology Press, 2017) Duraj, Szymon; Kopeć, Paweł; Kubale, Marek; Pikies, Tytus

In this paper, we consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that our problem can be solved to optimality in polynomial time under some restrictions imposed on the number of machines, their speeds, and the structure of the incompatibility graph. The theoretical considerations are accompanied by computer experiments with a certain model of scheduling.