Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 8

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  bipartite graphs
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Note on cyclic decompositions of complete bipartite graphs into cubes

100%
Fronček D.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
219-227
EN
So far, the smallest complete bipartite graph which was known to have a cyclic decomposition into cubes $Q_d$ of a given dimension d was $K_{d2^{d-1}, d2^{d-2}}$. We improve this result and show that also $K_{d2^{d-2}, d2^{d-2}}$ allows a cyclic decomposition into $Q_d$. We also present a cyclic factorization of $K_{8,8}$ into Q₄.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

An attractive class of bipartite graphs

100%
Boliac R., Lozin V.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
293-301
EN
In this paper we propose a structural characterization for a class of bipartite graphs defined by two forbidden induced subgraphs. We show that the obtained characterization leads to polynomial-time algorithms for several problems that are NP-hard in general bipartite graphs.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Isomorphic components of Kronecker product of bipartite graphs

100%
Jha P., Klavžar S., Zmazek B.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 2
301-309
EN
Weichsel (Proc. Amer. Math. Soc. 13 (1962) 47-52) proved that the Kronecker product of two connected bipartite graphs consists of two connected components. A condition on the factor graphs is presented which ensures that such components are isomorphic. It is demonstrated that several familiar and easily constructible graphs are amenable to that condition. A partial converse is proved for the above condition and it is conjectured that the converse is true in general.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Independent cycles and paths in bipartite balanced graphs

100%
Orchel B., Wojda A.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
535-549
EN
Bipartite graphs G = (L,R;E) and H = (L',R';E') are bi-placeabe if there is a bijection f:L∪R→ L'∪R' such that f(L) = L' and f(u)f(v) ∉ E' for every edge uv ∈ E. We prove that if G and H are two bipartite balanced graphs of order |G| = |H| = 2p ≥ 4 such that the sizes of G and H satisfy ||G|| ≤ 2p-3 and ||H|| ≤ 2p-2, and the maximum degree of H is at most 2, then G and H are bi-placeable, unless G and H is one of easily recognizable couples of graphs. This result implies easily that for integers p and k₁,k₂,...,kₗ such that $k_i ≥ 2$ for i = 1,...,l and k₁ +...+ kₗ ≤ p-1 every bipartite balanced graph G of order 2p and size at least p²-2p+3 contains mutually vertex disjoint cycles $C_{2k₁},...,C_{2kₗ}$, unless $G = K_{3,3} - 3K_{1,1}$.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Towards a characterization of bipartite switching classes by means of forbidden subgraphs

100%
Hage J., Harju T.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
471-483
EN
We investigate which switching classes do not contain a bipartite graph. Our final aim is a characterization by means of a set of critically non-bipartite graphs: they do not have a bipartite switch, but every induced proper subgraph does. In addition to the odd cycles, we list a number of exceptional cases and prove that these are indeed critically non-bipartite. Finally, we give a number of structural results towards proving the fact that we have indeed found them all. The search for critically non-bipartite graphs was done using software written in C and Scheme. We report on our experiences in coping with the combinatorial explosion.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Magic and supermagic dense bipartite graphs

100%
Ivanco J.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
583-591
EN
A graph is called magic (supermagic) if it admits a labelling of the edges by pairwise different (and consecutive) positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper we prove that any balanced bipartite graph with minimum degree greater than |V(G)|/4 ≥ 2 is magic. A similar result is presented for supermagic regular bipartite graphs.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

γ-labelings of complete bipartite graphs

100%
Bullington G., Eroh L., Winters S.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 1
45-54
EN
Explicit formulae for the γ-min and γ-max labeling values of complete bipartite graphs are given, along with γ-labelings which achieve these extremes. A recursive formula for the γ-min labeling value of any complete multipartite is also presented.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Extremal bipartite graphs with a unique k-factor

100%
Hoffmann A., Sidorowicz E., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
181-192
EN
Given integers p > k > 0, we consider the following problem of extremal graph theory: How many edges can a bipartite graph of order 2p have, if it contains a unique k-factor? We show that a labeling of the vertices in each part exists, such that at each vertex the indices of its neighbours in the factor are either all greater or all smaller than those of its neighbours in the graph without the factor. This enables us to prove that every bipartite graph with a unique k-factor and maximal size has exactly 2k vertices of degree k and 2k vertices of degree (|V(G)|)/2. As our main result we show that for k ≥ 1, p ≡ t mod k, 0 ≤ t < k, a bipartite graph G of order 2p with a unique k-factor meets 2|E(G)| ≤ p(p+k)-t(k-t). Furthermore, we present the structure of extremal graphs.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.