Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "bipartite graphs" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-14 z 14
    Tytuł:
    Note on cyclic decompositions of complete bipartite graphs into cubes
    Autorzy:
    Fronček, Dalibor
    Powiązania:
    https://bibliotekanauki.pl/articles/744154.pdf
    Data publikacji:
    1999
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hypercubes
    bipartite graphs
    factorization
    Opis:
    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₄.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1999, 19, 2; 219-227
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Magic and supermagic dense bipartite graphs
    Autorzy:
    Ivanco, Jaroslav
    Powiązania:
    https://bibliotekanauki.pl/articles/743476.pdf
    Data publikacji:
    2007
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    magic graphs
    supermagic graphs
    bipartite graphs
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2007, 27, 3; 583-591
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    γ-labelings of complete bipartite graphs
    Autorzy:
    Bullington, Grady
    Eroh, Linda
    Winters, Steven
    Powiązania:
    https://bibliotekanauki.pl/articles/744504.pdf
    Data publikacji:
    2010
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    γ-labelings
    bipartite graphs
    multipartite graphs
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2010, 30, 1; 45-54
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    An attractive class of bipartite graphs
    Autorzy:
    Boliac, Rodica
    Lozin, Vadim
    Powiązania:
    https://bibliotekanauki.pl/articles/743515.pdf
    Data publikacji:
    2001
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    bipartite graphs
    structural characterization
    polynomial algorithm
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2001, 21, 2; 293-301
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Extremal bipartite graphs with a unique k-factor
    Autorzy:
    Hoffmann, Arne
    Sidorowicz, Elżbieta
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/743924.pdf
    Data publikacji:
    2006
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    unique k-factor
    bipartite graphs
    extremal graphs
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2006, 26, 2; 181-192
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Isomorphic components of Kronecker product of bipartite graphs
    Autorzy:
    Jha, Pranava
    Klavžar, Sandi
    Zmazek, Blaž
    Powiązania:
    https://bibliotekanauki.pl/articles/971945.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Kronecker product
    bipartite graphs
    graph isomorphism
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 2; 301-309
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Independent cycles and paths in bipartite balanced graphs
    Autorzy:
    Orchel, Beata
    Wojda, A.
    Powiązania:
    https://bibliotekanauki.pl/articles/743087.pdf
    Data publikacji:
    2008
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    bipartite graphs
    bi-placing
    path
    cycle
    Opis:
    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}$.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2008, 28, 3; 535-549
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Towards a characterization of bipartite switching classes by means of forbidden subgraphs
    Autorzy:
    Hage, Jurriaan
    Harju, Tero
    Powiązania:
    https://bibliotekanauki.pl/articles/743415.pdf
    Data publikacji:
    2007
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    switching classes
    bipartite graphs
    forbidden subgraphs
    combinatorial search
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2007, 27, 3; 471-483
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A Characterization for 2-Self-Centered Graphs
    Autorzy:
    Shekarriz, Mohammad Hadi
    Mirzavaziri, Madjid
    Mirzavaziri, Kamyar
    Powiązania:
    https://bibliotekanauki.pl/articles/31342444.pdf
    Data publikacji:
    2018-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    self-centered graphs
    specialized bi-independent covering (SBIC)
    generalized complete bipartite graphs (GCB)
    Opis:
    A graph is called 2-self-centered if its diameter and radius both equal to 2. In this paper, we begin characterizing these graphs by characterizing edge-maximal 2-self-centered graphs via their complements. Then we split characterizing edge-minimal 2-self-centered graphs into two cases. First, we characterize edge-minimal 2-self-centered graphs without triangles by introducing specialized bi-independent covering (SBIC) and a structure named generalized complete bipartite graph (GCBG). Then, we complete characterization by characterizing edge-minimal 2-self-centered graphs with some triangles. Hence, the main characterization is done since a graph is 2-self-centered if and only if it is a spanning subgraph of some edge-maximal 2-self-centered graphs and, at the same time, it is a spanning supergraph of some edge-minimal 2-self-centered graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 1; 27-37
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Optimal edge ranking of complete bipartite graphs in polynomial time
    Autorzy:
    Hung, Ruo-Wei
    Powiązania:
    https://bibliotekanauki.pl/articles/743901.pdf
    Data publikacji:
    2006
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph algorithms
    edge ranking
    vertex ranking
    edge-separator tree
    complete bipartite graphs
    Opis:
    An edge ranking of a graph is a labeling of edges using positive integers such that all paths connecting two edges with the same label visit an intermediate edge with a higher label. An edge ranking of a graph is optimal if the number of labels used is minimum among all edge rankings. As the problem of finding optimal edge rankings for general graphs is NP-hard [12], it is interesting to concentrate on special classes of graphs and find optimal edge rankings for them efficiently. Apart from trees and complete graphs, little has been known about special classes of graphs for which the problem can be solved in polynomial time. In this paper, we present a polynomial-time algorithm to find an optimal edge ranking for a complete bipartite graph by using the dynamic programming strategy.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2006, 26, 1; 149-159
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On {a, b}-Edge-Weightings of Bipartite Graphs with Odd a, b
    Autorzy:
    Bensmail, Julien
    Inerney, Fionn Mc
    Lyngsie, Kasper Szabo
    Powiązania:
    https://bibliotekanauki.pl/articles/32361745.pdf
    Data publikacji:
    2022-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    neighbour-sum-distinguishing edge-weightings
    bipartite graphs
    odd weights
    1-2-3 Conjecture
    Opis:
    For any S ⊂ ℤ we say that a graph G has the S-property if there exists an S-edge-weighting w : E(G) → S such that for any pair of adjacent vertices u, v we have ∑e∈E(v) w(e) ≠ ∑e∈E(u) w(e), where E(v) and E(u) are the sets of edges incident to v and u, respectively. This work focuses on {a, a+2}-edge-weightings where a ∈ ℤ is odd. We show that a 2-connected bipartite graph has the {a, a+2}-property if and only if it is not a so-called odd multi-cactus. In the case of trees, we show that only one case is pathological. That is, we show that all trees have the {a, a+2}-property for odd a ≠ −1, while there is an easy characterization of trees without the {−1, 1}-property.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 1; 159-185
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Vertex-Distinguishing IE-Total Colorings of Complete Bipartite Graphs Km,N(m < n)
    Autorzy:
    Chen, Xiang’en
    Gao, Yuping
    Yao, Bing
    Powiązania:
    https://bibliotekanauki.pl/articles/30146641.pdf
    Data publikacji:
    2013-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    complete bipartite graphs
    IE-total coloring
    vertex-distinguishing IE-total coloring
    vertex-distinguishing IE-total chromatic number
    Opis:
    Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C(u) be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt(G), and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. VDIET colorings of complete bipartite graphs Km,n(m < n) are discussed in this paper. Particularly, the VDIET chromatic numbers of Km,n(1 ≤ m ≤ 7, m < n) as well as complete graphs Kn are obtained.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 2; 289-306
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Placing bipartite graphs of small size II
    Autorzy:
    Orchel, Beata
    Powiązania:
    https://bibliotekanauki.pl/articles/972020.pdf
    Data publikacji:
    1996
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    packing of graphs
    bipartite graph
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1996, 16, 2; 93-110
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    One-Three Join: A Graph Operation and Its Consequences
    Autorzy:
    Shalu, M.A.
    Devi Yamini, S.
    Powiązania:
    https://bibliotekanauki.pl/articles/31341697.pdf
    Data publikacji:
    2017-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    one-three join
    bipartite-join
    homogeneous set
    odd hole-free graphs
    Opis:
    In this paper, we introduce a graph operation, namely one-three join. We show that the graph G admits a one-three join if and only if either G is one of the basic graphs (bipartite, complement of bipartite, split graph) or G admits a constrained homogeneous set or a bipartite-join or a join. Next, we define ℳH as the class of all graphs generated from the induced subgraphs of an odd hole-free graph H that contains an odd anti-hole as an induced subgraph by using one-three join and co-join recursively and show that the maximum independent set problem, the maximum clique problem, the minimum coloring problem, and the minimum clique cover problem can be solved efficiently for ℳH.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 3; 633-647
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-14 z 14

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies