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: 18

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  bipartite graph
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

Placing bipartite graphs of small size II

100%
Orchel B.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 2
93-110
EN
In this paper we give all pairs of non mutually placeable (p,q)-bipartite graphs G and H such that 2 ≤ p ≤ q, e(H) ≤ p and e(G)+e(H) ≤ 2p+q-1.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A note on domination in bipartite graphs

100%
Gerlach T., Harant J.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 2
229-231
EN
DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

2-placement of (p,q)-trees

80%
Orchel B.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 1
23-36
EN
Let G = (L,R;E) be a bipartite graph such that V(G) = L∪R, |L| = p and |R| = q. G is called (p,q)-tree if G is connected and |E(G)| = p+q-1. Let G = (L,R;E) and H = (L',R';E') be two (p,q)-tree. A bijection f:L ∪ R → L' ∪ R' is said to be a biplacement of G and H if f(L) = L' and f(x)f(y) ∉ E' for every edge xy of G. A biplacement of G and its copy is called 2-placement of G. A bipartite graph G is 2-placeable if G has a 2-placement. In this paper we give all (p,q)-trees which are not 2-placeable.
4
Content available remote

Maximum Semi-Matching Problem in Bipartite Graphs

80%
Katrenič J., Semanišin G.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
559-569
EN
An (f, g)-semi-matching in a bipartite graph G = (U ∪ V,E) is a set of edges M ⊆ E such that each vertex u ∈ U is incident with at most f(u) edges of M, and each vertex v ∈ V is incident with at most g(v) edges of M. In this paper we give an algorithm that for a graph with n vertices and m edges, n ≤ m, constructs a maximum (f, g)-semi-matching in running time O(m ⋅ min [...] ) Using the reduction of [5] our result on maximum (f, g)-semi-matching problem directly implies an algorithm for the optimal semi-matching problem with running time O( [...] log n).
5
Content available remote

On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs

80%
Czap J., Przybyło J., Škrabuľáková E.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
141-151
EN
A graph G = (V, E) is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite 1-planar graphs with prescribed numbers of vertices in partite sets. Bipartite 1-planar graphs are known to have at most 3n − 8 edges, where n denotes the order of a graph. We show that maximal-size bipartite 1-planar graphs which are almost balanced have not significantly fewer edges than indicated by this upper bound, while the same is not true for unbalanced ones. We prove that the maximal possible size of bipartite 1-planar graphs whose one partite set is much smaller than the other one tends towards 2n rather than 3n. In particular, we prove that if the size of the smaller partite set is sublinear in n, then |E| = (2 + o(1))n, while the same is not true otherwise.
6
Content available remote

On Double-Star Decomposition of Graphs

80%
Akbari S., Haghi S., Maimani H., Seify A.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
835-840
EN
A tree containing exactly two non-pendant vertices is called a double-star. A double-star with degree sequence (k1 + 1, k2 + 1, 1, . . . , 1) is denoted by Sk1,k2. We study the edge-decomposition of graphs into double-stars. It was proved that every double-star of size k decomposes every 2k-regular graph. In this paper, we extend this result by showing that every graph in which every vertex has degree 2k + 1 or 2k + 2 and containing a 2-factor is decomposed into Sk1,k2 and Sk1−1,k2, for all positive integers k1 and k2 such that k1 + k2 = k.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Counterexample to a conjecture on the structure of bipartite partitionable graphs

80%
Gibson R., Mynhardt C.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
527-540
EN
A graph G is called a prism fixer if γ(G×K₂) = γ(G), where γ(G) denotes the domination number of G. A symmetric γ-set of G is a minimum dominating set D which admits a partition D = D₁∪ D₂ such that $V(G)-N[D_i] = D_j$, i,j = 1,2, i ≠ j. It is known that G is a prism fixer if and only if G has a symmetric γ-set. Hartnell and Rall [On dominating the Cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24 (2004), 389-402] conjectured that if G is a connected, bipartite graph such that V(G) can be partitioned into symmetric γ-sets, then G ≅ C₄ or G can be obtained from $K_{2t,2t}$ by removing the edges of t vertex-disjoint 4-cycles. We construct a counterexample to this conjecture and prove an alternative result on the structure of such bipartite graphs.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A proof of the crossing number of $K_{3,n}$ in a surface

80%
Ho P.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
549-551
EN
In this note we give a simple proof of a result of Richter and Siran by basic counting method, which says that the crossing number of $K_{3,n}$ in a surface with Euler genus ε is ⎣n/(2ε+2)⎦ {n - (ε+1)(1+⎣n/(2ε+2)⎦)}.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Path and cycle factors of cubic bipartite graphs

80%
Kano M., Lee C., Suzuki K.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
551-556
EN
For a set S of connected graphs, a spanning subgraph F of a graph is called an S-factor if every component of F is isomorphic to a member of S. It was recently shown that every 2-connected cubic graph has a {Cₙ | n ≥ 4}-factor and a {Pₙ | n ≥ 6}-factor, where Cₙ and Pₙ denote the cycle and the path of order n, respectively (Kawarabayashi et al., J. Graph Theory, Vol. 39 (2002) 188-193). In this paper, we show that every connected cubic bipartite graph has a {Cₙ | n ≥ 6}-factor, and has a {Pₙ | n ≥ 8}-factor if its order is at least 8.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Vertex-dominating cycles in 2-connected bipartite graphs

80%
Yamashita T.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 2
323-332
EN
A cycle C is a vertex-dominating cycle if every vertex is adjacent to some vertex of C. Bondy and Fan [4] showed that if G is a 2-connected graph with δ(G) ≥ 1/3(|V(G)| - 4), then G has a vertex-dominating cycle. In this paper, we prove that if G is a 2-connected bipartite graph with partite sets V₁ and V₂ such that δ(G) ≥ 1/3(max{|V₁|,|V₂|} + 1), then G has a vertex-dominating cycle.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Hamilton cycles in split graphs with large minimum degree

80%
Tan N., Hung L.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 1
23-40
EN
A graph G is called a split graph if the vertex-set V of G can be partitioned into two subsets V₁ and V₂ such that the subgraphs of G induced by V₁ and V₂ are empty and complete, respectively. In this paper, we characterize hamiltonian graphs in the class of split graphs with minimum degree δ at least |V₁| - 2.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Random procedures for dominating sets in bipartite graphs

80%
Artmann S., Harant J.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 2
277-288
EN
Using multilinear functions and random procedures, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Pₘ-saturated bipartite graphs with minimum size

80%
Dudek A., Wojda A.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
197-211
EN
A graph G is said to be H-saturated if G is H-free i.e., (G has no subgraph isomorphic to H) and adding any new edge to G creates a copy of H in G. In 1986 L. Kászonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size sat(n;Pₘ) of Pₘ-saturated graph of order n. They gave the number sat(n;Pₘ) for n big enough. We deal with similar problem for bipartite graphs.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On vertex stability with regard to complete bipartite subgraphs

80%
Dudek A., Żak A.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 4
663-669
EN
A graph G is called (H;k)-vertex stable if G contains a subgraph isomorphic to H ever after removing any of its k vertices. Q(H;k) denotes the minimum size among the sizes of all (H;k)-vertex stable graphs. In this paper we complete the characterization of $(K_{m,n};1)$-vertex stable graphs with minimum size. Namely, we prove that for m ≥ 2 and n ≥ m+2, $Q(K_{m,n};1) = mn+m+n$ and $K_{m,n}*K₁$ as well as $K_{m+1,n+1} - e$ are the only $(K_{m,n};1)$-vertex stable graphs with minimum size, confirming the conjecture of Dudek and Zwonek.
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Potentially H-bigraphic sequences

80%
Ferrara M., Jacobson M., Schmitt J., Siggers M.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
583-596
EN
We extend the notion of a potentially H-graphic sequence as follows. Let A and B be nonnegative integer sequences. The sequence pair S = (A,B) is said to be bigraphic if there is some bipartite graph G = (X ∪ Y,E) such that A and B are the degrees of the vertices in X and Y, respectively. If S is a bigraphic pair, let σ(S) denote the sum of the terms in A. Given a bigraphic pair S, and a fixed bipartite graph H, we say that S is potentially H-bigraphic if there is some realization of S containing H as a subgraph. We define σ(H,m,n) to be the minimum integer k such that every bigraphic pair S = (A,B) with |A| = m, |B| = n and σ(S) ≥ k is potentially H-bigraphic. In this paper, we determine $σ(K_{s,t},m,n)$, σ(Pₜ,m,n) and $σ(C_{2t},m,n)$.
16
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Isomorphic components of direct products of bipartite graphs

80%
Hammack R.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
231-248
EN
A standard result states the direct product of two connected bipartite graphs has exactly two components. Jha, Klavžar and Zmazek proved that if one of the factors admits an automorphism that interchanges partite sets, then the components are isomorphic. They conjectured the converse to be true. We prove the converse holds if the factors are square-free. Further, we present a matrix-theoretic conjecture that, if proved, would prove the general case of the converse; if refuted, it would produce a counterexample.
17
Content available remote

Minimal fixed point sets of relative maps

71%
Zhao X. Z.
Fundamenta Mathematicae
|
1999
|
tom 162
|
nr 2
163-180
EN
Let f: (X,A) → (X,A) be a self map of a pair of compact polyhedra. It is known that f has at least N(f;X,A) fixed points on X. We give a sufficient and necessary condition for a finite set P (|P| = N(f;X,A)) to be the fixed point set of a map in the relative homotopy class of the given map f. As an application, a new lower bound for the number of fixed points of f on Cl(X-A) is given.
18
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Dominating bipartite subgraphs in graphs

71%
Bacsó G., Michalak D., Tuza Z.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
85-94
EN
A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite 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ć.