Use this tag for questions in graph theory. Here a graph is a collections of vertices and connecting edges. Use (graph) instead if your question is about graphs of functions.
0
votes
1answer
28 views
Question related to a proof about the multiplicity of some eigenvalues
I have a question related to Lemma 4.2 from this pdf (which is, btw quite a nice exposition of Hoffman Singleton work on the classifications of Moore graphs of diameter 2 and 3.)
We are given a $n ...
0
votes
1answer
15 views
quick question on showing every edge in a graph of minimum degree n+1 is contained in a hamiltonian circuit.
Show that if every vertex in a graph on $n$ vertices has degree at least $\frac{n+1}{2}$, then every edge $e\in E(G)$ in G is contained in a Hamiltonian circuit.
My battle strategy: We know that ...
2
votes
1answer
21 views
Graph theory: Prove $k$-regular graph $\#V$ = odd, $\chi'(G)> k$
I'm looking to prove that any $k$-regular graph $G$ (i.e. a graph with degree $k$ for all vertices) with an odd number of points has edge-colouring number $>k$ ($\chi'(G) > k$).
With Vizing, I ...
5
votes
1answer
26 views
Lower bounds on the number of edges in a nonplanar graph
Let $e$ be the number of edges and $v \geq 3$ the number of vertices in a graph $G$. We know that if $G$ is planar, then $e \leq 3v-6$. My question is the opposite. Is there some sort of inequality ...
1
vote
0answers
30 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 ...
0
votes
2answers
37 views
Why don't all transitive graphs with a single loop define a category?
I'm reading Abstract & Concrete Categories: The Joy of Cats. On exercise 3A(c), the author defines the graph of a category C to be the large graph whose vertices are the objects in C, and whose ...
0
votes
1answer
19 views
Difference and relation between dependency graph and graphical model?
From page 2 of
http://www.mpi-inf.mpg.de/departments/d1/teaching/ss11/ProbMethod/files/lll.pdf
Let $A_1 , A_2 , \dots, A_n$ be $n$ events on a probability space $Ω$.
The dependency graph is a ...
3
votes
3answers
46 views
When a directed graph is represented in matrix form, what is the interpretation of the inverse of this matrix?
Let $G$ be a directed (unweighted) graph with $n$ nodes. We can represent $G$ with an $n \times n$ binary matrix $A$, with $A_{ij} = 1$ if there is an edge $i \to j$ and $A_{ij} = 0$ otherwise.
...
0
votes
1answer
24 views
Graph parameters that are equal for small graphs
Do you know of any pretty well known graph parameters which are equal for all small graphs (for $|G|$ small)? That is, there exist two parameters $a(G)$ and $b(G)$ such that $a(G) = b(G)$ for all ...
2
votes
1answer
44 views
Possible relation between spectra bounds of two matrices
A Laplacian matrix $L\in\mathbb{R}^{n\times n}$, is a symmetric matrix with entries, \begin{equation}
l_{ij}=\begin{cases} 1=\sum_{i,~ i\neq j} w_{ij} &\mbox{if } i=j \\
-w_{ij} & ...
1
vote
2answers
67 views
Determining the equivalence of two statements
I have been given two statements and told that they are equivalent, but I'm having a hard time convincing myself of that. The two statements are:
(1) "Every graph G has a minimum colouring in which ...
0
votes
1answer
32 views
Maximal subtrees of connected graph
Are all maximal subtrees of a simple connected graph isomorphic?
any hints?
1
vote
2answers
24 views
Existence of $k$-regular trees with $n$ vertices
a $k$-regular tree is a tree for which all vertices have a degree of $k$ or $1$ (internal veritces have a degree of $k$ and the leaves have a degree of $1$).
I've been asked to find for which values ...
0
votes
0answers
31 views
It is possible to partition the vertex set of a graph $V=V_1\cup V_2$ so that …
so that at most half of all edges run within each part. This is seen by, for example, http://math.stackexchange.com/a/210609/44285
I am also asked to show that in addition to the above, one may also ...
0
votes
0answers
19 views
Which graphs satisfy this property?
I am currently looking into a conjecture in graph theory, known as the Jackson conjecture (1992). It says the following, in an equivalent formulation to its equivalent statement:
*Conjecture*Every ...
