Results 11 to 20 of about 96,628 (243)
The Bipartite-Splittance of a Bipartite Graph
Discussiones Mathematicae Graph Theory, 2019 A bipartite-split graph is a bipartite graph whose vertex set can be partitioned into a complete bipartite set and an independent set. The bipartite- splittance of an arbitrary bipartite graph is the minimum number of edges to be added or removed in ...
Yin Jian-Hua, Guan Jing-Xin
doaj +3 more sources
Symmetric Bipartite Graphs and Graphs with Loops [PDF]
Discrete Mathematics & Theoretical Computer Science, 2014 We show that if the two parts of a finite bipartite graph have the same degree sequence, then there is a bipartite graph, with the same degree sequences, which is symmetric, in that it has an involutive graph automorphism that interchanges its two parts.
Cairns, Grant, Mendan, Stacey
core +8 more sources
Homomorphisms of infinite bipartite graphs onto complete bipartite graphs [PDF]
Czechoslovak Mathematical Journal, 1983 Let B be a bipartite graph on the vertex sets C, D. A homomorphism \(\phi\) of B onto a complete bipartite graph \(K_{r,s}\) is said to be bicomplete if \(\phi(x)=\phi(y)\) only if either both x, y belong to C, or both x, y belong to D. For a connected bipartite graph B, the author defines the parameter \(\beta_ 0(B)\) as the supremum of all values of ...
Bohdan Zelinka
openalex +4 more sources
European Journal of Combinatorics, 1996 Graphs that are obtained from single edges and even cycles by successive amalgamations are called cellular graphs. Especially cellular bipartite graphs are investigated in this paper. Since graphs with their shortest-path metrics are particular instances of finite metric spaces, these investigations are done from a metric point of view.
Hans‐Jürgen Bandelt, Victor Chepoi
openalex +3 more sources
The Connectivity of a Bipartite Graph and Its Bipartite Complementary Graph [PDF]
Parallel Processing Letters, 2020 In 1956, Nordhaus and Gaddum gave lower and upper bounds on the sum and the product of the chromatic number of a graph and its complement, in terms of the order of the graph. Since then, any bound on the sum and/or the product of an invariant in a graph [Formula: see text] and the same invariant in the complement [Formula: see text] of [Formula: see ...
Yingzhi Tian, Huaping Ma, Liyun Wu
openaire +4 more sources
On bipartite‐mixed graphs [PDF]
Journal of Graph Theory, 2018 AbstractMixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this article, we consider the case where such graphs are bipartite. As main results, we show that in this context the Moore‐like bound is attained in the case of diameter , and that bipartite‐mixed graphs of diameter do not exist.
Dalfó Simó, Cristina +2 more
openaire +5 more sources
Packing bipartite graphs with covers of complete bipartite graphs [PDF]
Discrete Applied Mathematics, 2010 AbstractFor a set S of graphs, a perfect S-packing (S-factor) of a graph G is a set of mutually vertex-disjoint subgraphs of G that each are isomorphic to a member of S and that together contain all vertices of G. If G allows a covering (locally bijective homomorphism) to a graph H, i.e., a vertex mapping f:VG→VH satisfying the property that f(u)f(v ...
Chalopin, Jérémie, Paulusma, Daniël
openaire +6 more sources
Treewidth of Chordal Bipartite Graphs [PDF]
Journal of Algorithms, 1995 Summary: Chordal bipartite graphs are exactly those bipartite graphs in which every cycle of length at least six has a chord. The treewidth of a graph \(G\) is the smallest maximum cliquesize among all chordal supergraphs of \(G\) decreased by one.
Ton Kloks, Dieter Kratsch
openalex +8 more sources
Concatenating Bipartite Graphs
The Electronic Journal of Combinatorics, 2022 Let $x,y\in (0,1]$, and let $A,B,C$ be disjoint nonempty stable subsets of a graph $G$, where every vertex in $A$ has at least $x|B|$ neighbours in $B$, and every vertex in $B$ has at least $y|C|$ neighbours in $C$, and there are no edges between $A,C$.
Chudnovsky, M +4 more
openaire +3 more sources
Embedding into Bipartite Graphs [PDF]
SIAM Journal on Discrete Mathematics, 2010 16 pages, 2 ...
Peter Heinig +2 more
openaire +3 more sources