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
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
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
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
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
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
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
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
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 ...
1
vote
0answers
56 views

Can you consider a directed graph the discretization of a 2-manifold equipped with a vector field?

Can you consider a directed graph the discretization of a 2-manifold equipped with a vector field? Thanks
1
vote
0answers
260 views

Understanding dependency graph for a set of events

From a note Definition 4. Let $\mathcal{E}_1 , \mathcal{E}_2 , \dots, \mathcal{E}_n$ be n events on a probability space $Ω$. The dependency graph is a directed graph $D = (V, E)$ on the set of ...
1
vote
0answers
98 views

maximum number of graph min-cuts, when edge-connectivity $c$ is odd

Based on the cactus representation of minimum cuts, it would seem that for a graph with $n$ vertices and edge-connectivity $c$, where $c$ is odd, that the maximum number of min-cuts is something like ...
1
vote
0answers
68 views

Finding the minimum length of an addition chain

It is known that for every positive integer $n$ there exists one or more optimal addition chains of minimum length. It is rumored that finding the length of the optimal chain is NP-hard, and the ...
1
vote
0answers
255 views

Number of odd cycles in non-bipartite 3-connected graph

By going over the tests of previous years in graph theory, I've come across an interesting (in my opinion) question: $G$ is 3-connected, non-bipartite graph. Prove that $G$ contains at least 4 odd ...
1
vote
0answers
50 views

Unions of edge sets of cycles in a graph

Given a connected graph with minimum degree 3 and a set of edges in this graph, I wish to find the number of decompositions of this edge set into cycles of the graph. I use decompositions in the ...
1
vote
0answers
77 views

Four questions concerning dual graphs

What are the (combinatorial/algebraic) conditions that the dual - resp. the (weak dual) - of a planar graph is unique (independent of its embedding), simple (and not a multi-graph)? Are these ...
1
vote
0answers
222 views

Perfect matching in $r$-connected graph

$G$ is a simple $r$-connected ($r \geq 1$) graph, with even number of vertices. Assume that $G$ doesn't contain $K_{1,r+1}$ as an induced subgraph. Prove that $G$ has a perfect matching. Now, I can ...
1
vote
0answers
119 views

Shifted Young tableaux & Hook numbers & Bulgarian Solitaire

I would like to find articles or documentation regarding this process: Starting from what ever integer partition, e.g. 5,2 for the number 7. Construct his Young tableaux and then fill it with Hook ...
1
vote
0answers
56 views

how to calculate the spectrum and inertia of sign pattern matrix?

I want to know how to calculate the spectrum and inertia of sign pattern matrix, how to use Nilpotent-Jacobian method to solve the problem about determinating spectrally arbitrary and inertially ...
1
vote
0answers
87 views

Tricky computations in graph theory proof

Let $0 < p < 1$ be a constant, and set $b = 1/p$. Let $0 < \epsilon < 1/2$. Given a natural number $r \ge 2$, let $n_r$ be the maximal natural number for which $\binom{n_r}{r} ...
1
vote
0answers
56 views

Bridge in a multigraph

According to Wikipedia, "a bridge in an undirected graph is an edge whose deletion increases the number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in ...
1
vote
0answers
128 views

General theory of graph coloring

In Ben Steven's article Colored graphs and their properties I read: We "color" a graph by assigning various colors to the vertices of that graph. [...] this process of coloring is generally ...
1
vote
0answers
46 views

How to sample the walk which visits each vertex of a graph specific number of times?

Is there any MCMC mathod that allow me to uniformly sample from all feasible walks where the following restrictions apply: ...
1
vote
0answers
141 views

Classifying graphs by patterns in their adjacency matrices

Given a set $S$, how can we classify different graphs $G(S)$ (tree, connected/disconnected, ...) based on the patterns of the 1's and 0's in their adjacency matrices $M(G(S))$?
1
vote
0answers
98 views

Bounding box for netwokx graph using matplotlib

I have tried to make a graph out of x,y co-ordinates from an area and display it using matplotlib but all the nodes sort of got overlapped as there is little difference between the when compared to ...
1
vote
0answers
52 views

An optimization involving (random) graphs

Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $-1$. Call this a configuration $\sigma \in \{+1,-1\}^n$. The number of $+1$s that we have to assign is ...
1
vote
0answers
140 views

Randomly Generating Connected Directed Acyclic Graphs

I'm looking for a way to generate random connected directed acyclic graphs, where I can specify the number of vertices that have no outgoing edges (leaf vertices). Anyone ever seen such a thing, or ...
1
vote
0answers
438 views

the number of shortest path between two points

I know that visibility graph is used to determine the shortest path between two points a mong a set of obstacles in the plane. So in the case that obstacles are triangles, is the maximal number of ...
1
vote
0answers
113 views

Shortest path variation

I'm looking for a solution to the following problem, related to shortest path. You are given a directed Graph $G = (V,E)$, source $s$, targets $t_1, t_2, \cdots , t_k$ and costs $c_{ij}$ for ...