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
13 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
0
votes
0answers
11 views

are graphs/networks additive

I was wondering if networks/graphs are the sum of their parts. Let's say you have a 15-node network. The spectral density of that network has X kurtosis and Y skewness. You also have a 20-node ...
0
votes
1answer
19 views

Graph Theory into

Let M and N be matchings in a graph G with (cardinality of M) > (cardinality of N). Prove that there exists matchings M' and N' such that (Cardinality of M') = ((cardinality of M)-1), and (Cardinality ...
1
vote
1answer
12 views

Minor Proof on a maximal planar graph

Let $G$ be a maximal planar graph of order at least $6$. Let $x$, $y$ be two non-adjacent vertices in $G$. Then $G + xy$ contains both $K_5$ and $K_{3, 3}$ as a topological minor. I am lost on this ...
0
votes
0answers
16 views

Graph theory proofs

I am trying to prove that half of the vertex cover of graph is less than it's matching number. The problem is I don't know how to start and what the solution should be like, please help!
1
vote
1answer
43 views

A sequence of $n^2$ real numbers which contains no monotonic subsequence of more than $n$ terms

I'm following a Combinatorics course at the moment, and have recent proved the Erdős–Szekeres Theorem (or, at least, some variation of): A sequence of length $n^2 + 1$ either contains an ...
1
vote
0answers
25 views

Random Spanning Tree Edge Probability

I am working on a problem with a Loop Erased Random Walk used to create random spanning trees from a graph. The problem has many parts, but there are two hints to help with the more complicated ...
-1
votes
1answer
14 views

Find a graph $H$ such that $H$ is a minor of $G$ but not a topological minor of $G$. [on hold]

Let $G$ and $H$ be simple graphs. Find a graph $H$ such that $H$ is a minor of $G$ but not a topological minor of $G$. Any ideas of how to do this problem? Any help is greatly appreciated, thanks.
0
votes
1answer
11 views

Measure for presence of several poorly interconnected components in undirected graph

Is there a measure to classify networks regarding whether or not they are composed of several (internally closely connected) groups which are poorly connected (i.e. few links between groups). That ...
0
votes
1answer
5 views

Scale free networks (power law)

I'm working with a dataset, of which I'm analysing the degree distribution. I'm finding that it obeys the famous power law/scale free degree distribution $\propto k^{-\gamma}$, but the value of ...
0
votes
1answer
21 views

Is my idea of incoming/outgoing arcs correct?

I'm reading Jungnickel's Graphs, Networks and Algorithms. I've met the following lemma: I know that $e^{-}$ are the incoming vertices and $e^{+}$ are the outgoing vertices. Then I've tried to ...
1
vote
2answers
30 views

Whether the graphs G and G' given below are isomorphic

Whether the graphs G and G' given below are isomorphic?
4
votes
2answers
28 views

Graph contains triangle

Prove that if a simple graph of order n has more than n^2/4 edges then it contains a triangle. I know Martels theorem states the opposite condition for a triangle free graph but I'm not sure how to ...
0
votes
2answers
15 views

Node with loop graph completion

Is a graph consisting of a single node complete in addition to being simple? What about a node with a self loop:it's not simple but is it complete ?
1
vote
1answer
25 views

graph theory - clique graph

I am trying to understand the concept of clique graph. So I found this page. But I do not understand the example and what "graph intersection" is. Can somebody explain to me why $K_4$ is a clique ...
5
votes
0answers
49 views

Number of sets of vertices whose union of neighbours contains exactly $k$ vertices

Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows: For example, $g$ for $n=3$: If ...
0
votes
0answers
20 views

Lovasz number and bipartite complement

Let $G=(V,E)$ be a graph on $n$ vertices. An ordered set of n unit vectors $U=(ui|i∈V)⊂R^N$ is called an orthonormal representation of G in $R^N$, if $u_i$ and $u_j$ are orthogonal whenever vertices i ...
0
votes
0answers
10 views

Positive definite functions defined on the embedding of a planar graph in the plane

By way of motivation: Let $f:[0,1]\rightarrow\mathbb{R}^2$ and $g:\mathbb{S}_1\rightarrow\mathbb{R}^2$ be continuous injections, where $\mathbb{S}_1$ is the circle ($\mathbb{R}/\mathbb{Z}$). Then, ...
1
vote
0answers
15 views

Double circle representation using ideal rubber bands

Let $V$ be a 3-connected planar graph, $V^*$ be its dual graph. Let $(C_i : i \in V)$ and $(D_p : p \in V^*)$ be a collection of circles so that if any edge $\{i,j\}$ borders any faces $a$ and $b$, ...
1
vote
1answer
27 views

The circumference of a hypercube graph

How can I find the circumference of a hypercube graph? is easy to see that a n-dimensional hypercube have a $2n$-cycle, but I cant prove that it's the largest, can anybody help me?
0
votes
1answer
13 views

Every nonhamiltonian 2-connected graph has a theta subgraph

If a graph $G$ has a spanning cycle $Z$, then $G$ is called a Hamiltonian graph and $Z$ has a Hamiltonian cycle. A theta graph is a block with two nonadjacent vertices of degree 3 and all other points ...
6
votes
3answers
77 views

Secret Santa Perfect Loop problem

(n) people put their name in a hat. Each person picks a name out of the hat to buy a gift for. If a person picks out themselves they put the name back into the hat. If the last person can only ...
1
vote
1answer
29 views

Graph and one Sequence challenge

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
1
vote
1answer
12 views

P - bounded polyhedron, L - linear map. Show that L(P) is a bounded polyhedron

Let $P = \{x\in \mathbb{R}^n \ | \ Ax\leq b\}$ be a bounded polyhedron. Let $L:\mathbb{R}^n \rightarrow \mathbb{R}^k$ be a linear map. Show that $L(P):=\{L(x)\ | \ x\in P\}$ is a bounded polyhedron. ...
0
votes
0answers
14 views

Is this a Red-Black Tree?

I tried to build RBT (Red-Black Tree) via this way: I build a balanced binary search tree (much as I can) and then colored it... Now the Q is: if this is a legal RBT? At my opinion is yes, because ...
3
votes
1answer
51 views

Graph with only the identity as endomorphism

Is there a graph $G$ with more than one vertex such that the identity $\textrm{id}: G\to G$ is the only graph homomorphism from $G$ to itself? Is there even an infinite example?
1
vote
1answer
19 views

Show that $\delta(G) \geq 4$ if $\chi(G)=5$ and $\chi(G-v) =4$ for each vertex $v \in G$

Let G be a graph satisfying the following conditions: (1) $\chi(G)=5$ and (2) $\chi(G-v) =4$ for each vertex $v \in G$ Show that $\delta(G) \geq 4$. Answer given: Suppose $\delta(G) \leq 3.$ Let ...
0
votes
0answers
14 views

Graph Minor/Subdivision Proof

Prove that if $G$ contains a $K_5$ or $K_{3, 3}$ minor, then $G$ contains a $K_5$ or $K_{3, 3}$ subdivision. Any proofs or hints are greatly appreciated.
0
votes
1answer
16 views

Does the maximum cut implies the minimum flow?

Is it possible to reverse the result of the min-cut max-flow theorem and obtain the result that if you have the maximum cut, then you have the minimum flow? I've been thinking about it, but I have no ...
0
votes
0answers
10 views

Upper bound for graphs with no k-cliques

We know that for random graphs $G(n,p)$ we have: $P[X=0]\leq e^{-\Theta(E[X])}$ where $X$ denotes the number of k-cliques in the random graph. Can this fact be used to say anything about the number of ...
0
votes
0answers
5 views

Algorithm for creating a directed scale free network with a fixed amount of nodes

I'm trying to figure out an algorithm that produces a scale free, directed network, for which I can give the final amount of nodes as an input. Now, this is a little bit tricky for a few reasons, so ...
0
votes
1answer
20 views

Number of possible graphs from a reachability matrix?

I need to know how to work out how many possible different digraphs can be drawn from a given reachability matrix. It needs to be with the minimum number of arcs between the nodes within the graph ...
1
vote
1answer
17 views

Power set ordered by sum and Dijkstra shortest path

I've needed to enumerate the power set ordered by the sum of elements in each subset. Luckily I've found a nice solution here: Algorithm wanted: Enumerate all subsets of a set in order of increasing ...
0
votes
1answer
16 views

Number of graphs with M edges that does not contain K-clique

If we consider the space of graphs $G(n,M)$ with $n$ vertices and $M$ denotes the number of edges. Is there any way of upper bounding the number of graphs in this space that does not contain any ...
0
votes
1answer
13 views

Proof between max independent set cardinal and min vertex cover.

i'm tryign to solve this problem for my graph class, but I don't really know where to start. Be G a graph without isolated vertex,proof that it verifies that $\alpha \leq \beta$, where $\alpha$ is ...
0
votes
1answer
10 views

Clarification on Eulirian cycle proof

I have trouble in understanding this proof can some one clarify the following elements: (1)Why does it follow that if T has maximum length, then $v_0=v_k$?(2)What does E represent?(3)What does E(T) ...
0
votes
0answers
11 views

what is the name or class of such graphs: the probability that two nodes are connected is decided a function of the distance

Random geometric graph is: Randomly place N nodes in a topologic space, if the distance between two nodes is smaller than a specific value, then these two nodes are connected. Now, slightly ...
0
votes
0answers
23 views

Example of a k-matroid

Let the set $K_i = (S, I_i)$ be a matroid for each $i \in \{1 \ldots k\}$. We define $K = (S, I) $ where $I = \{ X \subset S $ | $ X \in \bigcap_{i=1}^k I_i\}$ The claim now is that $K$ is a ...
0
votes
0answers
4 views

Recommendation needed in graph theory and statistics to be used in football predictions.

The following is a very simple model of what I am working on. I just need some advice since I don't have graph theory background. Suppose that A played at home against B and won by 3 goal ...
1
vote
1answer
40 views

Minimum number of edges to ensure connectedness

Question: Consider a simple graph G with n vertices. What is the minimum number of edges that G must have in order to ensure that it is connected? Justify your answer. My attempt: Let G = $(V, E)$. ...
0
votes
1answer
15 views

given a point cloud of n points, create a convex shape that defines their outer limits

I have a point cloud. I find its 'centre' by averaging the coordinates of each point. I translate the cloud so the average is at the origin (for simplicity sake) I want to then create a convex shape ...
1
vote
0answers
32 views

What is the multiplicity of the largest eigenvalue of a graph?

The Laplacian of a graph is a symmetric positive semi-definite matrix and hence has all real eigenvalues. Is there any characterization for the multiplicity of the largest Laplacian (and/or Adjacency ...
1
vote
1answer
22 views

how we can understand from spectrum of laplacian matrix of a graph that this graph is regular or not .

how we can understand from spectrum of laplacian matrix of a graph that this graph is regular or not . if we consider $0=\mu_1 \leq \mu_2 \leq ...\leq \mu_n$ as the eigenvalue of laplacian matrix ,we ...
0
votes
1answer
30 views

Coloring edges of $K_n$ so each vertex has $l$ edges of each color.

Given $n$ for what values of $l$ can we color the edges so that each vertex $l$ edges of each color adjacent to it. The number of colors used is clearly $\frac{n-1}{l}$ Thank you in advance.
2
votes
2answers
52 views
+50

Is the product of (modified) adjacency matrices of two matchings necessarily symmetric?

Consider $n$ vertices, and two (not necessarily perfect) matchings $M_1$ and $M_2$. With the following definition of a (modified) adjacency matrix of a matching, can we claim that $A(M_1)\cdot A(M_2)$ ...
0
votes
0answers
9 views

For what values of $l$ is $K_n$ the disjoint union of $l$-regular graphs?

Given $n$ for what values of $l$ can we see $K_n$ as a disjoint union of $l$-regular graphs? By disjoing union I mean we don't add th same graph twice. Oh and the graphs don't need to be spanning. ...
0
votes
2answers
20 views

Assign integers to the vertices of $G$

Let $G=(V,E)$ be a directed acyclic graph. I have to write an algorithm to assign integers to the vertices of $G$ such that if there is a directed edge from vertex $i$ to vertex $j$, then $i$ is less ...
0
votes
1answer
22 views

Proving number of edges in F = n - k

So if we let F = (V,E) be a forest with n vertices and k connected components (trees), how can I prove that the number of edges in F = n - k ? I was thinking of using induction, but I'm super lost. ...
3
votes
1answer
57 views

Does a colouring of a graph on two colours always have certain kinda of circle

Is there a planar set of points $P$ $(|P|\geq 4)$ such that no matter how you colour the points with two colours you can always find four points on a circle so that all four of the point have the ...
2
votes
2answers
74 views

Can the complete graph $K_9$, be 2-coloured with no blue $K_4$ or red triangles?

I am working on the following problem on 2-coloured complete graphs: $K_9$ is coloured red and blue and contains no red triangle and no blue $K_4$ then every vertex must have red degree 3 and ...