Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

1
vote
0answers
84 views

Detecting a clustering matrix via the SVD

Is there any easy way to detect using the SVD that a matrix $A$ is an adjacency matrix of a graph with disjoint cliques (i.e. that $A$ is a clustering matrix?). Up to a reordering of columns a cluster ...
1
vote
0answers
32 views

finding the decomposition of Laplacian matrix with position of zero elements unchanged

I'd like to know whether it's possible to find the decomposition of a Lapalacian matrix $A$ $B^TB = A$ where $B$ has the same dimension with $A$ and the position of zero elements in $B$ is the same ...
1
vote
0answers
108 views

Matching Endpoints of Bipartite Graph

I am trying to work out this problem: Suppose that $G=(V,E)$ is a bipartite graph with bipartition $(V_1, V_2)$ and that $A \subseteq V_1$. Show that the maximum number of vertices of $V_1$ that ...
1
vote
0answers
52 views

Proving a Graph contains a $3$-cycle. [duplicate]

Given a graph $G$ with $n$ vertices, where $n$ is even, prove that if every vertex has degree $\frac{n}{2}+1$, then $G$ must contain a $3$-cycle. (A $3$-cycle is a set of $3$ vertices, $a$; $b$; ...
1
vote
1answer
63 views

Showing an upper bound on $\kappa(G)$

Let $\kappa(G)$ be the connectivity of a graph $G$, $|V| = n$ and $|E|=m$. For any graph $G$, prove that if $m \geq n-1$ then $$\kappa(G) \leq \lfloor \frac{2m}{n} \rfloor$$ What I know is that ...
1
vote
0answers
52 views

Graph Walk on Monotonic Sequence

Given an undirected connected graph with $E$ edges, arbitrarily each edge with a unique number between 1 and $|E|$. Show that there exists a path with monotone labels whose length is at least the ...
1
vote
0answers
389 views

Lazy caterer's sequence, cutting pizza into most pieces with n straight cuts. Graph theory proof.

is there a way to solve this problem using graph theory? I used Euler's formula to find that when you use the method in which every new line intersects the old line in different places gives you ...
1
vote
0answers
51 views

Hamiltonian of one and two unknots

Recently I calculated the Ising Hamiltonian of a Hopf link. First, I colored the Hopf link in a checker board pattern and drew the Seifert surface from it. Considering the shaded regions as vertices ...
1
vote
1answer
100 views

Graph isomorphic to symmetric group

Show why the symmetry group of the graph below is isomorphic to $S_3 \times S_2$. $S_3$ and $S_2$ are symmetric groups and $\times$ denotes direct product. *----------* /|\ | | | | ...
1
vote
0answers
49 views

Mean matching size

Suppose there is a simple bipartite graph $G(X,E,Y)$, where $|X|=n_1$, $|Y|=n_2$, $|E|=m$. The edges $E$ are chosen uniformly at random. The question is what is a mean value of the size of the ...
1
vote
0answers
67 views

How to make this inference: Degree of a node in a graph is significantly diffenrent from poisson distribution

I am working on Gene-Gene interaction graphs. I build a graph by adding edges between genes (nodes) which show statistical interaction in predicting a quantitative parameter value (say, brain volume) ...
1
vote
0answers
540 views

Proving Vizing's Theorem using Induction

So I would like to prove Vizing's theorem (let d be the maximum degree of any vertex in graph G, any graph can be edge-colored with d or d+1 colors) using induction on the edges of G...here's my ...
1
vote
1answer
47 views

Taxonomic relationship between hypergraph and graph

I am trying to build a taxonomy of graph types. A hypergraph is often defined as a generalization of a graph. Its edges (called hyperedge) can have more then 2 endpoints. From a taxonomic view point, ...
1
vote
0answers
46 views

What's the interested topic or applications about random graph, probabilistic method or combination?

I want to pick some topics or applications to do a project of a current course. Those topics should be related to graph theory, combinatorics, random graph, probabilistic method etc. Such as social ...
1
vote
0answers
139 views

Even edge sets and cut edge sets

A cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. This problem is two ...
1
vote
0answers
68 views

Corresponding Triangulations of an (n+2)-gon to n Segments Connecting n+1 Collinear Points

So I'm asked to count the number of ways of connecting n+1 collinear points with n line segments subjected to the following constraints: If the line is L 1) No segment passes below L. 2) Starting at ...
1
vote
0answers
44 views

Cactus graph representation of min-cuts — must the components be connected?

Suppose a graph $G$ has edge-connectivity $c$. The min-cuts of $G$ (the cuts of weight $c$) can be represented in terms of a cactus graph $H$. This is "well-known". Each vertex of $w \in H$ ...
1
vote
0answers
158 views

Two-commodity minimum cost flow with antisymmetric costs

I'm looking at a minimum-cost flow problem in directed acyclic graphs. We are given a DAG plus a cost function that maps an edge to a real-valued cost, and a capacity function that maps an edge to a ...
1
vote
0answers
71 views

Is there another way to define this kind of graph?

Let there be $3m$ (where $m$ is any counting numbers and $m\ge{2}$) copies of $C_4$. we denote each copy of $C_4$ as $C_4(i),\quad 1\le i \le 3m $. Let $v_j(i)\in V(C_4(i)),\quad 1\le j \le 4$ be ...
1
vote
1answer
203 views

Bipartite graphs/ cartesian product

Prove that G and H are bipartite if any only if G x H is bipartite. (G x H denotes cartesian product) I saw someone else asked the same question, but the reply is only a hint on how to solve it. I am ...
1
vote
0answers
142 views

Topological sort of a subgraph of a multigraph

Is there a good algorithm for doing a topological sort of a subgraph of a multigraph? More specifically, given a multigraph G and a node n in the graph. Consider the subgraph G' all the nodes ...
1
vote
0answers
23 views

What can we say about the liner graph of lexicographic product?

Let $G$ and $H$ be two graphs on vertex sets $V(G)$ and $ V(H)$, respectively. Then their lexicographic product $ G\circ H$ is a graph denoted by $ V(G\circ H)=V(G) \times V(H) $, and there is an edge ...
1
vote
0answers
102 views

When the lexicographic product of two graphs is edge transitive?

A graph $G$ is said to be edge transitive provided that, for any two edges $f$ and $g$ in $G$ , there is an automorphism of $G$ sending $f$ to $g$. Let $G$ and $H$ be two graphs on vertex sets $V(G)$ ...
1
vote
0answers
33 views

Models for multiple graphs

I am trying to understand how to model multiple graphs. To make that concrete, I have two distinct graphs $\{V_1, E_1\}$ and $\{V_2, E_2\}$ where $V_i$ and $E_i$ are the node sets and the edge lists ...
1
vote
0answers
62 views

Find a minor in a graph

Given a graph $G$ with $\varepsilon(G)\ge k \in \mathbb{N}$ , find a minor $H\prec G$ such that $\delta(H)\ge k\ge |H|/2$. Where $\varepsilon(G)$ is $|E(G)|/|V(G)|$, and $\delta(H)$ is the minimun ...
1
vote
0answers
174 views

Is there a simple interpretation of the eigenvectors of a graph (visualizable?)?

I want to understand eigenvectors obtain from graphs (adjacency matrices) in an analogous way as they are interpreted from principal component analysis of a set of images, which is easy:Eigenfaces ...
1
vote
0answers
85 views

Eulerian Graph characterization

Show that a connected graph $G$ is Eulerian if and only if every edge of $G$ lies on a odd number of cycles. I try to do it using that every Eulerian graph has every vertex of even degree, and I try ...
1
vote
0answers
84 views

Bipartite regular (connected) graphs: Cocliques of maximum size (using purely combinatorial arguments)

Suppose $G$ is a regular bipartite graph on $2n$ vertices with valency $k>0$. Prove that a coclique $C$ has size at most $n$, and that if $G$ is connected, equality can only hold if $C$ is ...
1
vote
1answer
382 views

5-color graph problem

I need to demonstrate that a graph that doesn't have odd disjunctive circuits is a five color graph. This is indeed for a homework. I need some suggestions on how to approach this problem. Any help is ...
1
vote
0answers
99 views

Define infinite path with a finite relation in a graph with Least Fixed Point logic

Least Fixed Point(LFP) logic (p. 37ff) is an extension of first order logic which enables the usage of the least fixed point of FO-definable operators. For example consider a graph $G=(V,E)$ and ...
1
vote
1answer
61 views

What kind of solid has a face adjacency graph whose spanning trees are not feasible nets

Was reading an introductory graph theory book, and it says that nets of solids can be represented using adjacency graphs, and new nets can be discovered by searching for all the spanning trees of the ...
1
vote
0answers
146 views

Probability that a random graph is an expander

I have a random graph $G = (V, E)$ and each edge is in the graph with probability $p$. I need to show that the probability that $G$ is $\delta$-edge-expander* when $\delta= \frac{np}{4}$ goes to $1$ ...
1
vote
0answers
88 views

Minimum cost path with variable costs and fixed number of steps

I'm facing with the following problem. Suppose to have a generic oriented graph with curl (there can be an edge from a node to itself). Suppose also that you have to perform a $n$-vertices-long ...
1
vote
1answer
114 views

Expressing a relationship in a graph using quantified logic

Express the following using quantified formulae for a simple undirected graph $G = (V,E)$. The predicate P({u,v}) is true when $\{u,e\}\in E$ and false otherwise. The diameter of $G$ is at most 2. ...
1
vote
0answers
54 views

edge appearance probability and conditional independence

So I'm doing research on graphical models and on page 362 of http://www.seas.upenn.edu/~taskar/pubs/aistats09.pdf, it says that "if $\beta_{uv}=0$ (i.e. weight of edge $uv$ is zero), edge $e_{uv}$ ...
1
vote
0answers
40 views

Normalized Cuts and Spectra

I'm looking for a fleshed out proof of the following theorem. Theorem: Let $G=(V,\mathbf{W})$ be an undirected, edge-weighted graph with normalized Laplacian $\mathbf{L}_N$. Furthermore, let ...
1
vote
0answers
29 views

Plane graph combinatorially isomorphic to one with all edges straight

I have this problem. I have to show that every plane graph is combinatorially isomorphic to a plane graph whose edges are all straight. I Also have an hint that says to give a plane triangulation and ...
1
vote
0answers
122 views

Connectivity of random graphs

I am studying a problem that I can model as a random graph. In the basic model, I have a set of vertices that I connect by adding edges. At each stage, I randomly select two vertices and add an edge ...
1
vote
1answer
163 views

Depth first search on graph

I have a homework problem I think I know the answer to, but want to double check Consider the graph with three nodes, $a$, $b$, and $c$, and the two arcs $a \rightarrow b$ and $b \rightarrow c$. ...
1
vote
0answers
392 views

Genetic algorithm for travelling salesman problem with multiple salesmen

I am trying to produce a good genetic algorithm for the travelling salesman problem with multiple salesmen. In other words, assume we are given a graph $G$ with $n$ vertices and $k$ edges connecting ...
1
vote
0answers
30 views

Is there a term for this kind of “partition”?

Can anyone tell me if there's a term for this concept? Given a DAG $D=(V,A)$, I have a collection of subsets of $V$. Let's call that collection $C = \{ S_1, S_2, \ldots, S_n \}$. ($S_1 \cup S_2 ...
1
vote
0answers
90 views

Quasiconvex and quasiconcave graphs

Can anyone show the difference between quasiconvex, quasiconcave and quasilinear graphs? I am confused, because all quasiconvex graphs seem to be quasilinear...
1
vote
1answer
130 views

Draw the composition of directed graphs?

Given a directed graph representing a relation $S$ on a finite set $F$. How do I draw the directed graphs representing the relation $S^2$, $S^3$, $\ldots$? Thanks!
1
vote
0answers
24 views

Definition of Chromatic class digraph of a m-coloured digraph

I have to prove that if $D$ is a m-coloured digraph, then $K(D) = K\big(C(D)\big)$ Where $C(D)$ is the chromatic transitive closure of $D$, which is a multidigraph with the same nodes and arcs of $D$ ...
1
vote
0answers
194 views

Can Hall's theorem be derived from Tutte–Berge formula?

Can Hall's theorem be derived from Tutte–Berge formula? Hall's theorem is for existence of X-saturated matching in a X,Y bipartite graph. Tutte–Berge formula is for maximum size of a matching: ...
1
vote
0answers
63 views

Finding expectation of size of a subgraph.

I have been trying to implement a algorithm but got stuck in finding expectation of the size of the subgraph. n - size of the network. d - at most number of communities a node could participate ...
1
vote
0answers
31 views

Terminology: a notion of a set of “chords” for arbitrary subgraphs

I'm considering a problem on random graphs, where it makes sense to look the edges which "touch" a connected component, but which do not belong to it. Consider a fixed graph $G$, where as usual we ...
1
vote
0answers
193 views

Score Sequences Of Tournaments And Isomorphism

There are a lot of papers on degree/score sequences of tournaments, starting on a given sequence, and constructing a tournament that has that degree sequence, and so forth. But what if you start at ...
1
vote
1answer
2k views

Graph Theory Shortest Path Problem via Matrix Operations in MatLab

Here is something that has been getting the best of me for past few days. Hopefully someone can point me get in the right direction. I have a graph G, and I need ...
1
vote
0answers
260 views

Finding all spanning trees of a strongly connected directed graph

I have a strongly connected directed graph with about 10 vertices and 20 edges, and would like to find all spanning trees anchored at each vertex. Is there a systematic way, or a tested ...