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
1answer
8 views

typical distance on lattice

Consider $V=\{1,\dotsc,k\}^d$ a $d$-dimensional lattice with $\{x,y\} \in E$ for $x,y \in V$ whenever $|x-y|_1=1$. Now we consider the typical distance, i.e. the distance of two uniformly at random ...
1
vote
0answers
22 views

Shortest path in divisors graph

There is a graph with $N$ vertices numbered from $1$ to $N$. Edge between $a$ and $b$ exists if and only if $a | b$ or $b|a$. If $a|b$ then the weight of the edge is $\frac{b}{a}$. If $b|a$ then the ...
0
votes
0answers
9 views

How to find the K-th thinnest paths in a graph

I'm looking for an algorithm to find the K-th thinnest paths in a directed graph (like Yen's algorithm for shortest paths). By "thinnest" I mean with the lowest weight per edge. For example, in this ...
0
votes
0answers
26 views

Can a Directed Acyclic Graph contain geometric information?

Can a Directed Acyclic Graph be sketched on top of a curved surface (and therefore contain geometric information)?
2
votes
1answer
18 views

Is the complement of interval graph an interval graph also?

In Graph Theory, IG is an interval graph, then the question is: Is the complement of IG also an interval graph? if so, then how can we prove it?
1
vote
0answers
34 views

Knowing number of nodes on a graph given depth and span

How can I know the maximum number of nodes in a graph, given that every node has degree K and that the graph has a diameter of at most ...
1
vote
1answer
13 views

Is there any real application of Max-Tolerance Graphs, Interval Graphs?

I have read one article about Max-Tolerance Graph:. Basically: Max-tolerance graphs can be regarded as generalized interval graphs, where two intervals $I_i$ and $I_j$ induce an edge in the ...
0
votes
0answers
53 views

Formulating shortest path (and tractable graphical model MAP) as submodular minimization

I'm trying to view maximum a posterior inference in discrete graphical model as a submodular minimization. For example, the linear chain model can be solved efficiently by the Baum-Welch algorithm. ...
1
vote
0answers
9 views

Reference requests on SP -graphs to outline its research areas

I want to understand SP graphs (series-parallel graphs) deeper for more elegant computation. I want to understand which area to research to understand sp-graph deeper: logical formalism? ...
1
vote
1answer
15 views

How many component has graph with 20 vertex at least 10 degree

How many maximum component can have a graph with 20 vertices and minimum 10 degrees? My proceeding: For first component I need one vertex with 10 degree and next 10 vertex. In sum 11 vertex. For ...
0
votes
1answer
21 views

Permutation Adjacency matrix

What is the name of a directed graph with a permutation matrix as its adjacency matrix? I mean if (N,E) is a graph and its adjacency matrix is a permutation matrix what is the suitable name for this ...
0
votes
1answer
45 views

What is a class of a graph?

I found this question on my textbook.What is the class of the graphs in which every Eulerian cycle is also a Hamiltonian cycle, but I don't understand what he means by class.
0
votes
1answer
34 views

Shortest path change in weighted graph

In a weighted graph does the shortest path between two vertices change if we add to all the weights the same positive number?
1
vote
1answer
30 views

Upper bound on chromatic number

Suppose I have a graph $G$ and a function $f:V(G) \to \mathbb{N}$ so that for all $v\in V(G)$ we have: $$| \{f(v)-f(w)\ge 0 \mid w \in N(v)\} | \le k.$$ Show that the chromatic number $\chi (G) \le ...
1
vote
2answers
39 views

Set Covering Problem for Weighted Graph

I am looking for solution of the following problem. Let $G$ be a weighted graph with (positive) weights. The length of a path in a weighted graph is the sum of the weights of the selected edges. The ...
0
votes
0answers
50 views

A good primer for Concrete Mathematics?

I've been watching MIT's Mathematics for Computer Science, from Fall 2010 whilst reading Concrete Mathematics. Honestly the topic seems like a hodgepodge of ideas. I can follow about 2/3 of the ...
0
votes
1answer
34 views

Graph models problem

10 children and 17 adults split into teams, say that they cooperated for a project with 2 children and 3 adults. Do they all tell the truth? Clarifying each adult i claims to have worked with three ...
0
votes
1answer
22 views

Is Bipartite Graph an Interval Graph if not, how can prove that?

Give a Graph $G(V,E)$ is a bipartite graph. How can we know if it is an Interval graph $IG$ or not? Is there any proof for : Bipartite Graph is not an Interval Graph #
1
vote
1answer
44 views

Can a simple undirected graph with 11 vertices and 53 edges have a Eulerian circuit?

I have gathered these but I can't connect them properly. The sum of the degrees of the vertices is 106. So d1+d2+d3+d4+d5+d6+d7+d8+d9+d10+d11=106 To have a eulerian circuit no vertex must have an odd ...
3
votes
1answer
53 views

Find Three Mutual Friends in a Mathematical Society

I am having trouble with the following combinatorics/graph theory problem: A mathematical society has three divisions (Pure, Applied, and Statistics), and exactly $n$ mathematicians in each ...
0
votes
1answer
21 views

Graph theory 2-connected graphs

So I have to prove that a 2-vertex-connected graph is also a 2-edge-connected graph, any ideas becuase I cant even start the proof.
3
votes
2answers
62 views

Show With High Probability, No Vertex Belongs to More than One Triangle

I am working on a random graphs problem, which is stated as follows: Suppose that $p = d/n$, where $d$ is constant. Prove that with high probability (w.h.p.), no vertex belongs to more than one ...
8
votes
1answer
115 views

How can the Hadwiger–Nelson problem depend on the axioms of set theory?

The wikipedia page on the Hadwiger Nelson problem says the following two things: The correct value may actually depend on the choice of axioms for set theory. and the problem is equivalent ...
1
vote
0answers
65 views

Weak, Regular, and Strong connectivity in directed graphs

There are 3 types of connectivity when talking about a directed graph $G$. 1) weakly connected - replacing all of $G$'s directed edges with undirected edges produces a connected (undirected) graph. ...
0
votes
1answer
33 views

Is there a graph that cannot be colored by k colors for k greater than its chromatic number? [closed]

Is there a graph that is not proper color-able using exactly k colors where k greater than the chromatic number (and smaller than number of vertices)?
2
votes
1answer
28 views

Simple Graph Degree Sequence Proof

Let G be a simple graph with degree sequence $(d_1,d_2,...,d_n)$. Prove that for each k, $0<k<n$: $$\sum_{i=1}^k d_i\le k(k-1)+\sum_{i=k+1}^n min(k,d_i)$$ I'm new to graph theory and proof ...
0
votes
1answer
52 views

How to know if two graphs are ismorphic or not?

For example in the picture above. I know that I need to calculate if both graphs have the same number of vertices and edges. But I don't know what I should do next to check if the graphs are ...
1
vote
2answers
59 views

The maximum number of girls you can accommodate in a row

I was playing around with the following problem: 'What is the maximum number of girls in a group of boys and girls that can be seated in a row of $x$ seats so that no $n$ girls are sat next to each ...
2
votes
0answers
26 views

Applications of Prüfer sequence

Reading a book about a graph theory I found out about Prüfer's sequences which converts a labeled tree of $n$ vertices into an array of $n-2$ numbers. I was actually pretty surprised by this and was ...
3
votes
2answers
43 views

Independence Number of A Given Graph

Take $i(G)$ to be the independence number of $G$, i.e. the maximum number of pairwise nonadjacent vertices in $G.$ I want to show that if $G$ has $n$ vertices and $\frac{nk}{2}$ edges where $k \geq ...
0
votes
1answer
34 views

Simple graph proving cardinality of a set is even

Let G be a simple graph, and let S be the set of vertices of even degree, and T be the set of vertices of odd degree. Prove that the cardinality (number of things in) T is even. I am new to graph ...
-1
votes
1answer
35 views

Is there a triangle in a complete graph with 6 vertices, and all edges colored with 2 colors?

I have complete graph of 6 vertices. I want to prove that if we color all the edges with 2 colors, there must be a triangle of one of the colors. I see that there are $15$ edges, the degree of each ...
3
votes
0answers
36 views

Automatic solver of four-color theorem?

Does anyone know of an app/online tool to automatically colour any map or image using the 4-colour theorem? (Taking a Black and white image as input).
3
votes
1answer
49 views

How many trees on N vertices have exactly k leaves?

I need help on the topic of counting labeled trees (with its nodes numbered from 1 to N) with exactly k leaves. I have thought about surjective functions that return the father of a node, but I'm not ...
4
votes
0answers
40 views

Calculate the resistance between 2 adjacent nodes on a shape using graph theory

In shapes like regular octahedron or dodecahedron, how can Graph Theory be used to calculate the resistance between two adjacent vertices? All edges are assumed to have unit resistance. Is there ...
22
votes
0answers
271 views

What is that thing that keeps showing in papers on different fields?

A few months ago, when I was studying strategies for the evaluation of functional programs, I found that the optimal algorithm uses something called Interaction Combinators, a graph system based on a ...
1
vote
2answers
32 views

Ensure a graph approximates an Erdős-Renyi random graph even as nodes are added

Suppose we have a graph $G$ where the number of nodes increases over time, e.g. whenever the mean number of edges per node exceeds some value (which may be a function of the number of nodes). What is ...
0
votes
1answer
15 views

Does the Markov Blanket of a node include the node itself?

The definition states the Markov Blanket includes the parents of the children of the node, so does this include the node itself too?
2
votes
1answer
26 views

Does a simple graph which consists of one vertex satisfy any edge or vertex connectivity?

I'm curious whether a simple graph which contains just one vertex is edge k-connected or vertex k-connected. Edge-k-connectivity: We theoretically can remove any number of edges and it stays ...
0
votes
0answers
19 views

Is the number of vertex-face colorings of a planar graph encoded in the Tutte polynomial?

A vertex-face coloring of a planar graph is where one simultaneously colors vertices and faces of the graph so no two adjacent vertices have the same color; no two adjacent faces have the same ...
0
votes
0answers
25 views

How to calculate explicitly Cheeger constant (also caled Cheeger number or Isoperimetric number)?

I want to calculate explicitly Cheeger constant (also caled Cheeger number or Isoperimetric number) for a graph G(V, E), but I haven't found any sources, algorithms or examples. I'm using this ...
2
votes
1answer
41 views

What is the average number of connected components in a Secret Santa graph?

$n$ of my friends are involved in a Secret Santa gift exchange -- in order, each person is assigned to give some other random person a gift. Everyone is giving a gift to exactly one other person and ...
5
votes
1answer
66 views

Possible all-Pentagon Polyhedra

If a polyhedron is made only of pentagons and hexagons, how many pentagons can it contain? With the assumption of three polygons per vertex, one can prove there are 12 pentagons. Let's not make that ...
-1
votes
1answer
37 views

Conditions for embedding between non-oriented graphs [closed]

I have the following assignment on my Algorithms Analysis course. Given two undirected graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ with $\operatorname{card} (V_1) < \operatorname{card} (V_2)$ ...
1
vote
1answer
29 views

How to find a planar graph if I know that it has 7 faces with certain sizes?

I can't figure out how to find a graphs with this properties: I have to find 2 non-isomorphic plane graphs which (each of them) have 7 faces, two of which are of size 3 and the rest of size 4. This ...
5
votes
1answer
250 views

2-edge colorable graph approximation

A 2 edge-colorable graph is a graph in which we can color the edges with two colors, in a way such that no edges of the same color share a vertex. Given a graph G = (V,E) I want to find a 2 ...
1
vote
0answers
25 views

Prove by induction a property of a tree graph

Prove by induction (and without the use of cycle definition) that if to delete a leaf vertex from a tree graph it will stay as a tree graph. I think Ive got it wrong but what I did is the following: ...
0
votes
1answer
57 views

Given a graph $G = (V, E)$, prove $e \leq \frac{n(n-1)}{2}$ for all $n$ [duplicate]

I'm trying to figure out to solve this problem: Given a graph $G = (V, E)$ prove $$e \leq \frac{n(n-1)}{2}$$ for all $n$, where $e$ is the number of edges and $n$ is the number of vertices. I'm ...
0
votes
1answer
18 views

In graph bundles, the permutation matrix $P(\gamma)$ symmetric?

Let F be a finite graph and let $\Phi$ be an $Aut(F)$-voltage assignment of graph G . $G\times^\Phi F$ denotes the F-bundle over G associated with $\Phi$. $\gamma \in Aut(F)$ ,let $P(\gamma)$ denote ...
0
votes
1answer
18 views

Maximum number of edge-disjoint cycles vs minimum number of edges in a cut

Let $G = \langle V,E \rangle$ be a directed graph, let $C(G)$ denote the maximal number of edge-disjoint cycles that can be packed into $G$, and let $D(G)$ denote the minimal size of a set $E' \subset ...