Questions tagged [bipartite-graphs]

For questions about graphs for which the set of vertices can be divided into two disjoint subsets such that no edge of the graph joins two vertices from same subset.

Filter by
Sorted by
Tagged with
0
votes
0answers
13 views

Let G be a connected graph with at least one cycle. Proof that G is biparthite when no cycle is odd [duplicate]

So i have this task i am a little bit lost how to approach this problem. Could anyone guide me trough it? Let G be a connected graph with at least one cycle. Proof that G is bipartite when no cycle is ...
0
votes
1answer
22 views

let $G$=$(V,E)$ be a connected, d- regular bigraph. Prove that for any v, $G'$ = $G$ \ ${v}$ is connected.

Let $G=(V,E)$ be a connected, $d$-regular bigraph. Prove that for any $v\in V$, $G' = G\setminus\{v\}$ is connected. $G$ is a bigraph, so $V = A\cup B$. $G$ is also $d$-regular, so $|A| = |B|$. I ...
0
votes
0answers
25 views

Mapping in graph and bipartite graphs

Let $G$ be a bipartite graph. In order to find a match in the $G$ diagram so that there are no unpaired elements in the set $A$, a necessary and sufficient condition is $|A-N(T)|\leq|B-T|$ that is ...
0
votes
0answers
35 views

Is there a regular bipartite graph where the minimum cuts are trivial?

My question is: Given integers $r$ and $k$, is there an $r$-regular bipartite graph $G = L \cup R$ with $|L| = |R| = k$, which is $r$-edge connected, and such that every minimum cut is trivial? I can ...
2
votes
2answers
42 views

Is $K_1$ bipartite?

I'm thinking that it could be trivially bipartite since it only has one vertex and no edges but I am still a little bit unsure about it being trivially bipartite.
0
votes
0answers
11 views

generate all connected bipartite graphs with given bipartition using nauty

Given a number of vertices in partition A and partition B, I want to generate all connected bipartite graphs. I have found the nauty software package and can generate all graphs of a specified class ...
0
votes
2answers
24 views

Does a bipartite graph without perfect matching exist?

I know that not all bipartite graphs have perfect matching, but I am having trouble coming up with an example (I'm a visual learner). Can someone give me a visual example of a bi[artite graph without ...
0
votes
0answers
36 views

Bipartite Graph No Matching [closed]

Can someone provide me, a resource that could explain the answer to this problem (see above)? What is the name of the method they use? I'm looking to a resource that could explain the answer since the ...
0
votes
0answers
19 views

Given a bipartite graph $G(V=(A,B),E)$ , $|E| =\frac{|A||B|}{k}$. Prove that there is a group-matched complete bipartite graph [closed]

I'm struggling with the following question: Let $G(V=(A,B),E)$ a bipartite graph, $|E| =\frac{|A||B|}{k}$. Prove that there is a complete bipartite graph $G(V=(A',B'),E')$ when $A'\subseteq A$ and $...
0
votes
1answer
12 views

Choose a subset of a bipartitie graph that equals to the cartesian product of two sets

For any bipartite graph $G=(L\cup R,E)$ with $|L|=|R|=n$, can we always choose subsets $L_1\subseteq L$ and $R_1\subseteq R$ with $|L_1|=|R_1|=n/c$, such that either $\forall~l\in L_1 ~\forall r\in ...
-1
votes
1answer
23 views

Graph Theory, Bipartite Graph Formula [closed]

Let Graph G = (A, B, E) be a bipartite graph. |A| = a, each vertex in A has degree x; each vertex in B has degree y. Whats a formula for the number of vertices in B ?
1
vote
1answer
43 views

How to show this bipartite graph has a matching saturating X?

Let $G$ a bipartite graph with partitions $X$, $Y$ such that all degrees in $X$ are at least one, and if $x\in X$ has an edge to $y$ then $d(x)\geq d(y)$. Show that there's a matching saturating X. I ...
0
votes
1answer
38 views

Bipartite graph with density $1/2$ can not be regular

Let $G=(V,E)$ be a (undirected and simplicial) graph and let $A,B\subseteq V$ be two subsets. The density of a pair of subsets $(X,Y)\subseteq A \times B$ is defined as $$d(X,Y):=\frac{|\{\text{edges ...
4
votes
3answers
47 views

Proving a bipartite graph does not have a perfect matching

I want to prove that for every $k \geq 1$, there exists a bipartite graph $G$ on sets $X$ and $Y$ such that $|X| = |Y|$, $\delta_{\min}(G) = k$ and $G$ has no perfect matchings. For starters, I know ...
1
vote
1answer
9 views

Number of maximum cliques in $n$- partite graph woth $2n$ vertices

Going through particular examples, it appears to me that a maximum clique of $n$-partite graph $G$ on $2n$ vertices is $n$-clique (clique of order $n$), when each partite contains exactly $2$ vertices....
0
votes
0answers
32 views

Number of perfect matchings in a $K_{m,n}$ bipartite graph? [duplicate]

How would you find the number of perfect matchings of a $K_{m,n}$ bipartite graph?
0
votes
0answers
25 views

wire bonding (graph theory - planar bipartite graph)

In IC industry there is something called wire bonding as showed in the picture: one is trying to put that (above one called block) onto the pad (pic in the below) , as centered as possible. As the ...
0
votes
0answers
16 views

Determine isomorphism classes for pairs of families from paths, cycles and bipartite graphs

Consider the family of graphs $A=\{\text{paths}\}$, $B=\{\text{cycles}\}$ and $D=\{\text{bipartite graphs}\}$. For each pair of these families, determine all isomorphism classes of graphs that belong ...
-1
votes
1answer
38 views

Probability that a bipartite graph G has a perfect matching [closed]

Let $G$ be a bipartite graph with $n$ left vertices, and $n$ right vertices on $n^2 − n + 1$ edges. Let $\pi$ and $\sigma$ be independent and uniformly random permutations of $1,2,...,n$. We want to ...
1
vote
1answer
83 views

Matching and Alternating chain Problem [closed]

Let $G$ be an arbitrary graph and let $M^{'} $ and $M^{''}$ be two matchings (not necessarily perfect) in $G$, with $|M^{'} | − |M^{''}| = t > 0.$ By definition: An alternating chain is an ...
2
votes
1answer
87 views

Question on perfect matching for bipartite graph

My question is: Let a bipartite graph $G = (V' \sqcup V'', E)$ have a perfect matching, let$|V'| = |V''| = n$, and let $\operatorname{deg} v ≥ t$ for every $v ∈ V'$. Prove that $G$ has at least $t!$ ...
3
votes
0answers
65 views

Problem related to matching ( Tutte's and Hall condition)

Let G be a graph without a perfect matching, thus, Tutte’s conditions fail for G which implies that there exists a set $S ⊂ V (G)$ such that the number of odd components in $G − S$ exceeds $|S|$. Now ...
1
vote
1answer
70 views

Spectrum of complete bipartite graph [closed]

I've been tasked with the following: Prove that a complete bipartite graph with n + m nodes has a spectrum $(\sqrt{mn} ,0,..,0,-\sqrt{mn})$ Prove that a complete graph with n nodes has a spectrum $(n-...
1
vote
1answer
52 views

Does such a bipartite graph exist?

In the course of my studies on graphs I sometimes use gadgets. I recently came upon a need for a certain bipartite graph with the following properties, and I am wondering if anyone knows if such a ...
1
vote
0answers
18 views

Matching in Bipartite (A,B) Graph with $|M| \geq 2/5 |A|$

Let $G$ be a bipartite graph with partitions $(A,B)$. Suppose for all $u \in A$, we have $\deg_G(u) \geq 4$ and for all $v \in B$, $\deg_G(v) \leq 10$. Prove that there exists a matching $M$ of $G$ ...
2
votes
0answers
23 views

Bipartite graphs that are not incidence graphs of hypergraphs

At Wikipedia one reads: "[...] most, but not all, bipartite graphs can be regarded as incidence graphs of hypergraphs. I wonder which bipartite graphs can not be regarded as incidence graphs of ...
0
votes
0answers
52 views

ε-regular pair (A, B) includes $K_{3,3}$ subgraph

Let G consist of just a single ε-regular pair (A, B) of density d > 0, with |A| = |B| = l. Prove that for any d, we have that if ε is sufficiently small and ` is sufficiently large, then we can ...
1
vote
1answer
31 views

What are “different” bipartite regular graphs?

I am struggeling with the idea that there are multiple CONNECTED $d$-regular bipartite graphs for fixed degree $d$ and number of vertices $2n$. If I just draw the vertices in two columns calling the ...
1
vote
0answers
35 views

Prove that the maximal number of linearly independent eigenvectors with eigenvalue 1 is equal to the number of connected components in $G$

Let $G$ be a simple graph containing $n$ nodes. Let $V$ be the set of all the nodes and $E$ the set of all edges in $G$. $$ \text{If } \left\{i, j\right\} \epsilon E, M_{ij} = \frac{1}{\text{deg}(j)}. ...
1
vote
0answers
21 views

The product of an eigenvector and its transpose in a bipartite graph

I was reading this proof on the eigenvectors of a bipartite graph I don't really understand the 3rd line of this proof. How do we know if there even exists such an eigenvector x1 such that $x_1^T*x_1$ ...
1
vote
0answers
19 views

Assignment problem with batching costs

I am studying an assignment problem with batching costs, and I would like to know if there is a standard name or algorithm for this problem. I know this problem can be formulated as mixed-integer ...
0
votes
1answer
39 views

What is the adjacency matrix for k-regular graphs, and for bipartite graphs?

What is the adjacency matrix for $k-$regular graphs, and for bipartite graphs? I suppose that the general form for the adjacency matrix of a bipartite graph is: \begin{equation*} A_{K_{n,\: m}}=\begin{...
0
votes
1answer
51 views

Determine which are true and which are false | Graph Theory

From the following statements determine which are true and which are false. In each case justify your answer or give a counterexample. a) If a connected graph has cut vertices, then also it has ...
0
votes
0answers
45 views

Determine the set of cut vertices, bridges and number of connected components.

In the following graphs, determine the set of cut vertices, bridges and number of connected components when removing cut vertices or bridges: a) Complete graphs b) Bipartite graphs c) Path d) Cycles e)...
2
votes
1answer
45 views

A question about the constructive proof of Kőnig's Theorem

Kőnig's Theorem is as follows: If $G$ is a bipartite graph, then the maximum number of edges in a matching in $G$ is equal to the minimum number of vertices in a vertex cover in $G$. The constructive ...
0
votes
1answer
32 views

Laplacian of bipartite graph

It is well know that in the case of weighted graph with positive weights, the dimension of the kernel of the Laplacian is the number of connected components of the corresponding graph. This fails when ...
0
votes
0answers
16 views

Algorithm for splitting bipartite graph in a disjoint subset

I am looking for an algorithm to split a bipartite graph into disjoint subsets. The problem originates from analyzing a cross-correlation matrix, $C_{nm}$, between two sets of variables. I convert ...
0
votes
0answers
29 views

Is there any new developments on the Barnette's conjecture?

When I searching for interesting math problems. I find there is a graph theory conjecture called the Barnette's conjecture. The statement is: Is every bipartite simple polyhedron Hamiltonian? A early ...
1
vote
2answers
56 views

Show that $G$ satisfies Hall's condition

Show that $G$ satisfies Hall's condition I knew the definition: Let $G$ be a bipartite graph with partite sets $U$ and $W$, where $r=|U|\leq|W|$. Then $G$ satisfies Hall's condition if, for every $S\...
0
votes
2answers
22 views

Show that the cartesian product of bipartite graph is also bipartite.

Let $G$ and $H$ be two bipartite graphs. Show that $G×H$ is a bipartite graph. Any idea how to start ?
0
votes
0answers
30 views

Maximum edges for bipartite graph where all vertices of one part have degree 1

I am looking for a method/algorithm to find the maximum edges possible for a bipartite graph where one part only has nodes of degree one. I guess a good example would be an algorithm matching as many ...
0
votes
0answers
75 views

Rule of double counting between Stirling numbers of first kind and second kind [duplicate]

I have no idea where to start, any help would be appreciated. sterling numbers of the 1st kind
1
vote
0answers
26 views

Number of Terms of $ \sum_V{\sum_H{\prod_i{\prod_j{\left( v_ih_j \right)}}\prod_i{\left( v_i \right)}\prod_j{\left( h_j \right)}}} $

I have the following equation for a bipartite graph, where each vertex $v_i$ is connected to every vertex $h_j$. Each value in either $H$ or $V$ could take one of two possible values $\{0,1\}$. We ...
1
vote
1answer
50 views

Matching in Bipartite Graphs - Saturation

I have the following question in my homework and I'm not sure how to go about proving it. Hall's Theorem states that the graph contains a matching saturating X is and only if |N(S)| >= |S| for all ...
0
votes
1answer
47 views

maximum edges of a bipartite graph

Show that if a graph G = (V,E) is bipartite, then it has at most n^2/4 edges if n is even, and at most (n^2 − 1)/4 edges if n is odd. Here n = |V| is the number of vertices in G. I want to prove this ...
1
vote
1answer
25 views

Tutte Berge Formula Simple Proof Clarification

I am trying to understand the one line proof of Tutte-Berge formula here in 24.1 (just the $\le$ side proof), i.e. $$ν(G) ≤ |U| + ν(G − U) ≤ |U| + \frac 1 2 (|V \setminus U| − o(G − U)) = \frac 1 2 (|...
1
vote
0answers
43 views

Bipartite Graph Construction

Assume $m$, $n$ to be positive integers. Given two partitions $[mn]=A_1 \cup A_2 \cup \dots \cup A_m$ and $[mn]=B_1 \cup B_2 \cup \dots \cup B_m$ of $[mn]$ into sets of cardinality $n$, show that the ...
1
vote
0answers
65 views

Effective resistance of weighted bipartite graph

Question: Let $K_{m,n}$ be a weighted complete bipartite graph with weights $w_{ij}$ for each edge $(i,j)$. What is the effective resistance $R_{i,j}$ between any two nodes of the graph? I am ...
0
votes
1answer
65 views

The (largest) bipartite subgraph

I'm looking for any idea or algorithm that solves the problem of finding bipartite subgraphs in any graph. In general, I'd like to divide graph into the smallest number of bipartite subgraphs. My ...
1
vote
0answers
27 views

Combinatorics on subgraphs of the Hamming cube

Let $d \in \mathbb{N}$ even, and let's consider the bipartite graph $G_d$ that has nodes labeled on the left side by $\{x \in \{0,1\}^d : |x| = d/2\}$ and on the right side by $\{x \in \{0,1\}^d : |x| ...

1
2 3 4 5
12