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

0
votes
0answers
16 views

Induction over DAGs

I'd like to prove a proposition true over all valid Directed Acausal Graphs. I think I can do that by starting with a graph with one node and adding either a new node and connection, or a new valid ...
0
votes
1answer
30 views

Is Wikipedia incorrect about Eulerian tour?

Wikipedia's Eulerian Path states, An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single ...
1
vote
1answer
27 views

How many connected and undirected graphs are there when d(v) = 2 for every vertex in the graph.

Well, at the beginning I thought the answer would be (n-1)! But it's not correct. My assumption to that answer was that its just like putting n people in a circle, but it doesnt seem like its exactly ...
0
votes
0answers
14 views

Nyquist Limit Explanation

Kindly explain Nyquist in easy words . The actual question is . We can attempt to display sampled data by simply plotting the points and letting the human visual system merge the points into shapes. ...
4
votes
1answer
253 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...
1
vote
1answer
36 views

how do i find the shortest path/route/tour that visits every vertex at lest once

I have a non-directed non-weighted graph and i want to find the shortest path/route/tour (i don't know which is the correct definition) that visits every vertex at least once. Is there an algorithm ...
2
votes
1answer
18 views

Create a configuration - graph theory

I've encountered this (startling) difficult, to me, question: Create a configuration in the plane with a ring size 4, so that every internal vertex is of degree 5. Now, I assume I may not use ...
2
votes
2answers
29 views

Forming a simple polygon from the extrusion of a polygonal chain

Let's say I have a set of vertices connected by edges to form a polygonal chain. Each vertex may be shared by a number of edges to form various sub-chains. An example is shown below. Each edge has ...
1
vote
0answers
52 views

Prove the number of total dominating sets of a bipartite graph is not exactly divisible by $2$

here is a cute problem I created from another not so cute problem I made from a cute problem. Prove the number of total dominating sets of a bipartite graph is never exactly divisible by $2$ ( of the ...
1
vote
0answers
20 views

What does “total variation on a graph” mean? How can I visualize it?

There is a paper " The Total Variation on Hypergraphs -Learning on Hypergraphs Revisited" which I am reading and I was not able to appreciate the term "total variation" in terms of graph theory. ...
3
votes
1answer
69 views

Problem in Chromatic Number

The smallest number of colors needed to color a graph G is called its chromatic number, and is often denoted χ(G). lemma : If G has a degree sequence $ (d_1, d_2, ... , d_v) $ with $ d_1 \ge d_2 \ge ...
0
votes
4answers
24 views

For trees with $10$ vertices, consider those which have a vertex of degree $8$. What is the number of such trees?

I'm trying to figure out what is the flaw in my thinking for this practice question. If a tree has $10$ vertices, one of which must have degree of $8$, this means that we essentially have a $K_{1,8}$ ...
1
vote
1answer
30 views

Reduce problem to max flow

I have the following question: Assume each student can borrow at most 10 books from the library, and the library has three copies of each title in its inventory. Each student submits a list of ...
0
votes
2answers
265 views

what is the maximum number of non loop edges that can exist in an undirected graph

please tell me a equation to find maximum number of non loop edges that can exist in an undirected graph. for example if vertices are 10 then how many non loop edges can exist?
3
votes
1answer
34 views

Is this perfect matching probability game really open?

A friend of mine heard from a friend of his of the following problem that my friend's friend claims remains open? The game is as follows: There are 100 persons with different names, their names are ...
4
votes
1answer
64 views

The number of dominating sets of a bipartite graph is not exactly divisible by $2$

here is a cute problem I created from another cute problem. Prove the number of dominating sets of a bipartite graph is never exactly divisible by $2$. A dominating set of a graph is a set of ...
0
votes
1answer
24 views

Find all “critical nodes” in a graph

Say there is a graph in which every node is connected to every other by some path. How would i find the particular nodes, which if removed would lead to some of the nodes NOT being connected to all ...
0
votes
0answers
26 views

Percolation Theory Basics: Open cluster size decay (Square Lattice)

I am trying to learn some stuff about percolation. On wiki (http://en.wikipedia.org/wiki/Percolation_theory) it says: "when $p<p_{c}$, the probability that a specific point (for example, the ...
2
votes
1answer
47 views

Graphs without nontrivial automorphism

I'm trying to solve two problems about graph automorphisms. I want to construct a bipartite graph without a nontrivial automorphism. I want to find the smallest possible number of nodes for a graph ...
1
vote
1answer
21 views

Maximum Flow - Ford Fulkerson

I tried using the Ford Fulkerson algorithm with the following question: The result I got was 25: I've been told that my solution is not correct. I was not told what the solution was however. ...
1
vote
1answer
41 views

Planar Graph & block

a) Show that a graph is planar if and only if each of its blocks (maximal 2-connected subgraphs) is planar. b) Deduce that a minimal nonplanar graph is a simple block.
0
votes
1answer
114 views

network structure — k-cliques vs p-cliques

In network structure, what is the difference between k-cliques and p-cliques, can anyone give a brief explaination with examples? Thanks in advanced! ============================ EDIT: I found an ...
2
votes
1answer
55 views

Chromatic Number

The smallest number of colors needed to color a graph $G$ is called its chromatic number, and is often denoted $\chi(G)$. Show that if graph $G$ is simple, then $$ \chi \ge \frac{V^2}{V^2 - 2E}. $$
4
votes
1answer
39 views

What is the Laplacian Matrix used for?

You can turn graphs into several matrix forms depending on what data you want to focus on. Does the Laplacian form have any uses on its own, or does it need to be paired with other things as some ...
0
votes
1answer
22 views

Minimum vertices set bipartite graph covering-special case

I was wondering if anyone here could give me any pointers as to how to solve the following problem. Let B=(L,R,E) be an undirected bipartite graph, ∀u∈L, ∃ s= {ei(u,wi)} ∈E; i=1,2.....n connect u to ...
0
votes
1answer
46 views

Bipartite graph set cover

I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is an undirected bipartite graph G with the two vertex sets V1, V2. ...
1
vote
1answer
65 views

does a power law degree distribution imply graphs are sparse?

Lets say I have a random variable with values in the space of square binary matrices from which I can sample (adjacency matrices of) graphs, and lets say that the resulting graphs have a power law ...
1
vote
2answers
44 views

Proving the theorem of graph theory

I want to know the proof of the condition of a Euler walk or tour in a directed graph. I googled a lot about it from MIT courseware to some other YouTube channels but I couldn't find any proof for ...
1
vote
0answers
25 views

Litterature on Dynamic graph theory

I was wondering if anyone knows any good articles or papers or books on graph theory that deals with changing graphs and not just static ones. So far I've only found qualitative descriptions of ...
4
votes
2answers
67 views

What do they mean when they say “a blue $3$-regular subgraph”?

In page 4 of the following http://web.mat.bham.ac.uk/D.Kuehn/RamseyGreg.pdf the text says In any graph the number of vertices with odd degree must be even. For this reason there cannot exist a red ...
1
vote
1answer
28 views

Random graphs question regarding exponents

On page 19 http://www.iecn.u-nancy.fr/~chassain/GDT/documents/SpencerStFlour.pdf All in the first Paragraph. it gives an estimate of (they use equal instead of approximation) ...
1
vote
0answers
34 views

Using red/blue algorithm on graph with zero cycle

I have a graph where I am trying to find minimum spanning tree using the red rule, blue rule approach. Now the graph is a directed graph and it has a zero cost cycle near the terminal point. In fact ...
1
vote
1answer
19 views

Name for the type of relation similar to the edge set of a regular directed graph?

For a binary relation over a set, if each member in the set appears the same number of times in the first position and in the second position in the relation, is there a name for such a relation? For ...
2
votes
1answer
53 views

Show that $\chi(G)+\chi(G')\ge2\sqrt n$

I want to show that $\chi(G)+\chi(G')\ge2\sqrt n$ where $G'$ is the complement of some graph $G$ of order $n$. I've so far managed to show $\chi(G)+\chi(G')\le n+1$ (probably not too useful) and that ...
7
votes
3answers
823 views

the Nordhaus-Gaddum problems for chromatic number of graph and its complement

Is there any relation between the chromatic number of a graph $G$ and its complement $G'$ that are always true? I saw these ones: $\chi(G)\chi(G')\geq n$ and $\chi(G)+\chi(G')\geq 2n$, but I'm not ...
0
votes
1answer
22 views

Mathematical Predicate logic

Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent ...
2
votes
1answer
108 views

Counting triplets with red edges in each pair

Given a tree having N vertices and N-1 edges where each edges is having one of either red(r) or black(b) color. I need to find how many triplets(a,b,c) of vertices are there, such that on the path ...
0
votes
1answer
60 views

Example of non-Abelianness of symmetric group for graphs

I know that for $n \ge 3$, $S_n$ is non-Abelian. I would like to work out an example in terms of graphs so to make it sure that I understand it right. A symmetric group of graphs of four vertices, ...
0
votes
2answers
96 views

Difference between Topological Data Analysis and Graph Technology

I'm trying to understand the difference between Oracle's graph technology which apparently has an inherent understanding of topology and Ayasdi's Topological Data Analysis technology. Are these two ...
0
votes
1answer
26 views

Order of deletion and contraction to form a minor

I have been reading a couple of sites regarding minors and have come across the statement that the order of deletion and contraction of edges do not matter. Why is that the case? In fact, I came up ...
0
votes
0answers
22 views

Graph theory problem of directed graph

Given a directed graph how can one find whether there exists a path that has all the vertices connected in short how can one know whether there exists a spanning tree in a directed graph or not. ...
1
vote
1answer
39 views

If a k-regular graph is 1-factorable, then does it have chromatic index k?

Wikipedia says A k-regular graph is 1-factorable if it has chromatic index k. If I am correct, it means that if a k-regular graph has chromatic index k, then it is 1-factorable. Although it ...
6
votes
3answers
226 views

Number of acyclic digraphs on $[n]$ with $k$ edges and each indegree, outdegree $\leq 1$

How many (labelled) acyclic digraphs are there on the vertex set $[n]$ with exactly $k$ edges and each indegree, outdegree $\leq 1$? The answer is $${n \choose k} {n-1 \choose k} k!.$$ Is there a ...
3
votes
1answer
60 views

Error in my reasoning on $\dim_{VC}(H)=1\Rightarrow|H|\leq 1$?

Let $S$ be a set with $n$ elements. Let $P(S)=\{X\mid X\subseteq S\}$ Let $H\subseteq\mathcal{P}(S)$ (hypergraph with edge set $S$). Let $H_{|U}=\{U\cap A\mid A\in H\}$ Let ...
0
votes
1answer
30 views

Find the number of vertices in the graph

Let $n\ge 1$ and $V_n = (\left\{ 1,2,...n \right\}\rightarrow\left\{ 0,1,2 \right\})$. Let us define $G_n = \left<V_n, E_n \right>$. $f,g$, are two vertices. They are connected iff: $$\left|\{ i ...
2
votes
1answer
52 views

Mathematics of genealogical trees

I really searched a lot but did not find anything meeting my needs: A place where questions of genealogy, especially the structural and combinatorial analysis of genealogical "trees" of descendants ...
0
votes
1answer
36 views

Find $k$ non-disrupting paths from $s$ to $t$

Given the bidirectional graph $G = (V, E)$ where $V$ = set of Vertices, $E$ = set of Edges; given source node $s$ and destination node $t$. Let $A_i$ ($i = 1, 2,\ldots l$) be the subset of vertices ...
0
votes
1answer
29 views

3-color Graph colouring

Given a directed graph such that each node has indegree=outdegree=1 devise a algo that colour the graph such that no adjacent nodes has same color. **Note:**there is no self loop and graph has to be ...
1
vote
1answer
35 views

Let $G$ be a graph of girth $5$ for which all vertices have degree $\geq d$. Show that $G$ has at least $d^2+1$ vertices.

Could someone verify this? Pick a vertex $v$ of $G$. Pick distinct vertices $u_1, u_2, \ldots, u_d$ incident with $v$. Note that this can be done since $v$ has no loops and degree $\geq d$. For each ...
0
votes
1answer
38 views

Identity in the 9 lectures in random graphs

In the 9 lecures in random graphs on pages 16/17 http://www.iecn.u-nancy.fr/~chassain/GDT/documents/SpencerStFlour.pdf they say let $n_{0}(k)$ be the minimum $n$ for which $\binom{n}{k} ...