# Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

4,096 questions
Filter by
Sorted by
Tagged with
2answers
12 views

### How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?

In Dijkstra's original paper, he talks about two problems related to graphs. The second one is the problem of finding the shortest path between two nodes, which is what is most commonly meant by ...
0answers
7 views

### How to Draw the planar embedding of a graph?

I am very interested to know how to Draw the planar embedding of a graph,I found this question from a friend, I cannot, find the planar embedding because it is a petersen graph and is not planar but ...
1answer
18 views

### How many colors will be used in the following bipartite graph

I decided to create an algorithm to find the colors that is used to color a bipartite graph, the algorithm proceeds as follows: Rename the vertices in a some order $v_1,v_2,\ldots,v_n$. Do a single ...
0answers
18 views

### Using graph symmetries to speed up subgraph enumeration

I have an undirected graph $G$. It has some symmetries in the sense that I know it's automorphism group $Aut(G)$. I am searching for a specific subgraph defined by some constraints $\phi$ and ...
2answers
18 views

### Finding the perfect matching

This the following graph where I want to find the perfect matching and a maximum matching I converted this to an bipartite graph, and found that the perfect matching exists and also found an maximum ...
0answers
12 views

### Connected component- feature regions extraction

I'm trying to extract the connected component from a graph, in the following way: ...
1answer
62 views

0answers
31 views

### Min Cost Max Flow algorithms for providing multiple solutions

Minimum Cost Maximum Flow algorithms have been known to provide an optimal flow routing for network flow problems in satisfactory runtime. Some of the algorithms for solving a min-cost max-flow ...
0answers
53 views

### A simple graph $G$ with even clique number, find a subset $A$ of the vertices, subgraph induced by $A,V-A$ have equal clique number

Given a simple graph $G=(V,E)$ s.t. $2\mid \omega(G)$, Show that $\exists S\subseteq V\text{ s.t. } f_G(S)=f_G(V\setminus S)$ where $f_G(A)$ is the clique number of the sub-graph of $G$ induced by ...
0answers
36 views

### Prove that a graph $G =(V, E)$ verifying $|E|>\frac{(|V|-1)(|V|-2)}{2}$ is connected

Prove that a graph $G =(V, E)$ verifying $|E|>\frac{(|V|-1)(|V|-2)}{2}$ is connected.
0answers
32 views

### Sub-graph Selection Algorithm Problem (Dynamic Programming or NP)

We have an algorithm problem in hand, can you please write your ideas about this, thank you! There are N many nodes with K different colors. Some of the nodes have direct connection between each other ...
1answer
19 views

### 1/2 Approximation to MAX-DICUT by rounding a linear program

Consider a graph $G=(V, A, w)$, where each arc $(u,v)\in A$ has a non negative weight $w_{u,v} \in \mathbb{R}^+$, partition $V$ into $U$ and $W$, $W=V-U$ such that $\sum_{(i,j)\in A} w_{i,j}z_{i,j}$ ...
1answer
20 views

### Property testing of a complete multipartite graph

Propose and prove an $\epsilon$-test for the following property in the dense graph model: $G=(V,E)$ is a complete multipartite graph. That is, there exists a partition $V=V_1\cup\ldots\cup V_\ell$ ...
2answers
59 views

### Graph with $\Theta(2^n)$ minimum $(s, t)$-cuts

Is there any graph with $\Theta(2^n)$ minimum $(s, t)$-cuts? Given an undirected graph $G = (V, E)$ and two distinct vertices $s$ and $t$ of $G$. A minimum $(s, t)$-cut is a $(S, T)$ cut of G which ...
1answer
33 views

### Applications of the splittance of a graph/ Turning graphs into splitgraphs

Let $G=(V,E)$ be a graph. For $C\subseteq V$ let $G[C]$ be the subgraph of $G$ induced by $C$. A split Graph is defined as follow: $G$ is a split graph if there exists a subset $C\subseteq V$ so that ...