Use this tag for questions in graph theory. Here a graph is a collections of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.
0
votes
0answers
11 views
find the smallest set of ordered components within a larger set
Let's consider a query set Q and a larger superset S. Each element of Q exists in S. The goal is to express Q using the smallest number of (connected) "components" of S.
Here is a concrete example:
...
2
votes
2answers
40 views
The existence of a graph homomorphism
Is there a graph homomorphism between the 6-hypercube (https://en.wikipedia.org/wiki/File:6-cube_graph.svg) and the cube (https://en.wikipedia.org/wiki/File:3-cube_graph.svg)?
1
vote
0answers
24 views
What would a Tutte Polynomial =0 represent?
So I'm working on proving (via contradiction) that the flow number $\phi(G)$ of a bridgeless graph $G$ is always defined. I'm using the flow polynomial, and I got to a point where I have $0=T(0,1-u)$.
...
1
vote
0answers
21 views
Visualizing directed preorders
I am trying to understand directed preorders, a.k.a. directed sets. Are they analogous to connected DAGs?
3
votes
2answers
34 views
In any tree, what is the maximum distance between a vertex of high degree and a vertex of low degree?
In any undirected tree $T$, what is the maximum distance from any vertex $v$ with $\text{deg}(v) \geq 3$ to the closest (in a shortest path sense) vertex $y$ with $\text{deg}(y) \leq 2$? That is, $y$ ...
2
votes
0answers
31 views
Minimum degree of a planar minimal 5-chromatic graph.
Let $G$ be a planar minimal 5-chromatic graph. That is, any of its proper subgraphs has chromatic number at most 4. I need to prove that its minimum degree is at least 5. I want to prove by ...
4
votes
2answers
75 views
Can a knight visit every field on a chessboard?
I was doing excercises about graphs theory and I came across a quite interesting excercise (which probably has something to do with Hamiltonian Cycle):
"Is it possible to step on every field of a 4x4 ...
2
votes
1answer
19 views
Factor-critical graphs
$G$ is factor-critical $\Leftrightarrow$ $c_o(G-U) \leq |U|$, $\forall U \subseteq V(G)$ except when $U = \emptyset$ (where $c_o$ is the number of odd components - basically, the RHS means that $U = ...
0
votes
0answers
19 views
Application of 0/1 network flows
Question: Let $D = (V,A)$ be a digraph. Describe how to efficiently find $X \subseteq V$ of minimum size such that $\exists$ a path from $X \to v$, $\forall v \in V-X$.
My thoughts: Create a source, ...
0
votes
1answer
29 views
Tutte's 1947 proof and paper on a family of cubical graphs
It is known that if a graph is connected, cubic, simple and $t$-transitive, then $t \le 5$. A proof is given in [Biggs, Algebraic Graph Theory, Chapter 18], and this result is due to [Tutte, ``A ...
0
votes
0answers
21 views
Flow network: prove at least one of the two statements is true
For any flow network N, add an edge $e_{ts}$ and color it black. Color all other edges in N with black, red or green, then at least one of the following two cases is true:
1) There exists a cycle C ...
0
votes
0answers
48 views
graphs where distance between every two vertices is $\geq$2.
Are there any class of graphs where distance between every two vertices is $\geq$2.
I was wondering about the existence of such graphs. Because for counter examples I have Paths $P_n$.
Thank you ...
1
vote
1answer
26 views
Prove that any circuit contains a cycle
This is a practice question (not HW)
Prove that any circuit in a graph must contain a cycle AND that any circuit that is not a cycle contains at least two cycles.
Note : This is for a first course ...
13
votes
1answer
124 views
Generalized nontransitive dice
Let $X_1, \ldots, X_n$ be a collection of random variables. Consider the directed graph with vertex set $\{ 1, 2, \ldots, n \}$ where there is a directed edge $i \to j$ if $\mathbb{P}(X_i > X_j) ...
4
votes
2answers
56 views
Why the root of this tree has to be “1”?
Arrange $2^{n-1}-1$ zeroes and $2^{n-1}$ ones in a balanced full binary tree of depth $n$. If we want the number of edges that connect the same (and respectively different) digits are the same, then ...
0
votes
0answers
46 views
Graph theory question - G is a graph which doesn't have unconnected vertices [duplicate]
Let $n$ be a natural number, $n\ge 2$. Let $G$ be a graph with $n$ vertices.
It is known that $G$ has exactly $2$ vertices with the same degree.
$G$ has no isolated vertices (each vertex has degree ...
1
vote
1answer
43 views
MATLAB code to find distance and eccentricity in graphs
I was trying to find the distances between vertices in graphs. But as the number of vertices are increasing up to 25 vertices or more, its becoming a tedious job for me to calculate $distance$ and ...
0
votes
2answers
37 views
Find all of the distinct non-planar graphs with 6 vertices.
Find all of the distinct non-planar graphs with 6 vertices. Draw a picture of each such graph, and explain why the graphs you have found are the only possibilities.
HINT: Proceed by cases, ...
0
votes
0answers
30 views
Prove that $T$ has a unique Hamiltonian path
Let $T$ be a tournament, and suppose that no two vertices of $T$ have the same score. Prove that T has a unique Hamiltonian path.
1
vote
0answers
35 views
Proof is needed for a lower bound of the maximal eigen-value of a non-negative, irreducible, integer matrix
$A$ is a non-negative, integer, irreducible, $m$ by $m$ matrix. It is well known (Perron-Frobenius) that $A$ has a positive eigen value (denote it by $\lambda$) with a positive eigen vector ($x$). It ...
3
votes
2answers
54 views
Proving a statement about $k$-colouring of a graph
Prove that a graph is $k$-colourable iff its edges can be oriented in such a way that the resulting directed graph does not contain a path of length $k$.
It seems to me that the '$\Leftarrow$' ...
0
votes
0answers
16 views
Algorithm for topological sorting without explicit edge list
Suppose I have a set of vertices $V$ and a function $f(V_1, V_2)$ which given two vertices returns +1 if there is an edge from $V_1$ to $V_2$, -1 if there is an edge from $V_2$ to $V_1$, and 0 ...
1
vote
1answer
33 views
Prove the edges of a multigraph may be oriented such that the net-degree of any vertex is $\leq 1$.
The net-degree of a vertex $v$, denoted $\text{netdeg}(v)$, in a digraph $G$ is defined by
$$ \text{netdeg}(v)=| ~ \text{outdeg}(v) - \text{indeg}(v) ~| $$
where $\text{outdeg}(v)$ and ...
2
votes
3answers
43 views
Check existence of cycle in graph with only number of vertices and their degree
I know that we can check existence of cycle in graph by simply traversing the graph and check whether the vertex has been visited.
However, if there are only number of vertices and their ...
1
vote
0answers
49 views
count the number of connected induced subgraphs in a graph with bounded degree
Let $G=(V,E)$ be a graph where the maximum degree of a vertex is 4. I've been asked to find an efficient algorithm for counting how many connected induced subgraphs are in $G$.
What I have so far is a ...
2
votes
2answers
26 views
Embedding of Tree
Q.
Proof for every Tree can be embedded into the plane.
Conditions.
We cannot use Euler Formula for Planar Graphs. We can use definition of tree, $V-E=1$, no-cycles, every edge is critical, there ...
4
votes
1answer
87 views
Prove that in a graph a group of even nodes there are two of degree at least $2$
We have just started learning graphs, and I understand the concept clearly, but when it comes to proving something I just don't know how to start!
Prove that in in a group of an even number of ...
7
votes
2answers
78 views
Build graph with exactly n automorphisms
Construct graph with exactly distinct n automorphisms. For n $\geq$ 2.
I wonder if we can just take an asymmetric graph, such as this one as building block.
2
votes
1answer
31 views
How to tell if a directed graph is acyclic from the adjacency matrix
Suppose you have an adjacency matrix $A$ for a directed graph $G=\{V,E\}$, so $A_{ij} = 1$ if $V_i\rightarrow V_j \in E$, and $A_{ij}=0$ otherwise. Many properties of the graph can be derived from ...
-2
votes
0answers
46 views
Is there graph folding? [closed]
Is there anything in graph theory that has a graph instantly "fold" down onto itself, (like a game of tetris maybe) when it gets to a certain formation?
1
vote
0answers
46 views
+50
Expansion vs Sparsest cut
let $G=(V,E)$ and $S\subsetneq V$ then expansion of set $S$ is
$$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}}$$
where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges ...
0
votes
0answers
16 views
stability number of random graphs with constant $p$ and $p=p(n)$
If we know that
$$ \lim_{n \rightarrow \infty} p\left(\alpha(G) \geq \frac{n}{2l}\right)=0$$
where $l$ is a positive integer, $p=p(n)$ is a function of $n$ such that $p \geq (6l\ln(n))/n$ for $n$ ...
13
votes
4answers
797 views
Are these 2 graphs isomorphic?
They meet the requirements of both having an = number of vertices (7)
They both have the same number of edges (9)
They both have 3 vertices of deg(2) and 4 of deg(3)
However, graph two has 2 ...
0
votes
0answers
34 views
Degree distribution of a random graph
I stuck on the following problem
If a given vertex in a random graph has degree $k$ with probability
$${{{n-1}}\choose{k}}p^k(1-p)^{n-1-k}$$
What can we conclude about degree distribution of $G$. ...
0
votes
1answer
30 views
Is there a formula to calculate the minimum height of an n-nary tree with L leaves?
I'm trying to figure out if there is a way to calculate the minimum height of an n-nary tree with L leaves. Is there such a formula?
0
votes
1answer
57 views
Prove that the existence of a bridge is an invariant
An invariant is a property $P$ that is shared by all isomorphic graphs. In other words, a property $P$ is an invariant provided that whenever $G_1$ and $G_2$ are isomorphic graphs, if $G_1$ satisfies ...
4
votes
2answers
53 views
How many vertices of degree 1 in a tree?
How many vertices of degree 1 are there in a tree with no vertices of degree more than 4?
The only thing that I have right now is that the number of edges in a tree is n-1 where n is the number of ...
1
vote
0answers
27 views
Graph Has Two / Three Different Minimal Spanning Trees?
I'm trying to find an efficient method of detecting whether a given graph G has at least two different minimal spanning trees. I'm also trying to find a method to check whether it has at least 3 ...
1
vote
3answers
39 views
Existence of a graph G? [duplicate]
The Q i am asked is as follows.
Q:Let G=(V,E) be a graph with nine vertices such that each vertex has a degree 5 or 6. Show that G has at least 5 vertices of degree 6, or at least 6 vertices of ...
0
votes
1answer
32 views
Question about bipartie graphs.
I have a fairly basic inquiry but i would sleep better at night if i saw a proof of it.
Q: i know that if i take a connected subgraph with at least 2 vertices of any simple bipartite graph G that it ...
1
vote
3answers
49 views
Does the following graph have a Hamilton circuit?
A Hamilton circuit (or path) is a path that visits each vertex exactly once (except the start/end point) and ends at the starting point.
I've stared at this for quite a while and cannot find a ...
2
votes
1answer
53 views
Does the kernel need to be the full automorphism group of the induced subgraph?
Let $\Gamma$ be a simple graph. Suppose its automorphism group $G=\text{Aut}\Gamma$ is imprimitive on its vertex set $V$. Take a block system $\mathcal{B}$ of $V$. Let $B\in\mathcal B$, and let ...
1
vote
2answers
65 views
Totally busted euler trail.
New to graph theory proofs would like some help.
Let $G_{1}$ and $G_{2}$ be Eulerian graphs . let $v_{1}$ be a vertex in $G_{1}$ and $v_{2}$ be a vertex in $G_{2}$ jion $v_{1}$ and $v_{2}$ by a ...
0
votes
2answers
74 views
Necessary and sufficient condition for an Euler trail between two vertices
Graph theory question one of those obvious math proofs so its going to be a pain to prove.
Show that G=(V,E) has an Euler trail between (different) vertices u and v if and only if G is connect and ...
0
votes
0answers
40 views
What is that type of TSP
I'm searching for the name of the TSP-like problem.
The basic principal is like it follows:
When a city is visited by the salesman, he will came in one point and exit the city in another. The ...
2
votes
2answers
68 views
Is it possible to have a walk between every two vertices of any arbitrary length in a graph?
I have a very basic question. I was going through the topic Walks in Graphs. I was just wondering: Is it possible to have a walk between every two vertices $x$ and $y$ of any arbitrary length $l$ in ...
1
vote
1answer
33 views
Find limits for functions of natural numbers
So I am dealing with some problems about random graphs where we find limits of functions of natural numbers. A simple example can be the limit of $\ln(n)$ as $n \rightarrow \infty$, where $n$ is the ...
1
vote
1answer
39 views
Calculating upper eccentricity in a graph
I was going through a paper. There calculating upper eccentricity was mentioned.
Can anybody help me in finding out how it was done? I tried hard but was unable to get it.
A little hint or explanation ...
7
votes
1answer
82 views
Is there a name for relations with this property?
Is there a name for relations $\rho : X \rightarrow Y$ such that for all $x,x' \in X$ and all $y,y' \in Y$ we have that the following conditions $$xy \in \rho$$ $$x'y \in \rho$$ $$xy' \in \rho$$ imply ...
1
vote
1answer
39 views
Determine no. elements in $ \operatorname{Aut}(H)$ where $H$ is the 6 point/5line graph in the shape of H
Determine the amount of automorphisms in the group $\operatorname{Aut}(H)$ where $H$ is the graph with 6 points and five lines in the shape of a capital 'H'. Here is what it should look like, I ...
