Tag Info

Hot answers tagged

6

Under a few assumptions, I compute that the shortest path requires 12 steps; the player should make the moves ESNNNWWSSSEN. (This is one step shorter than the two solutions you linked to.) The assumptions I made are: Entities which would step out of the game board do not move. All three entities step simultaneously. The player may not make a move which ...


4

No, this is not a counterexample. Change the green to yellow, and that's it.


3

Given weights $w(i,j)$ of edges $v_iv_j$. For $1\le i\le j\le n$ let $F(i,j)$ denote the minimal sum of a valid move sequence of the pawns from $(v_1,v_1)$ to $(v_i,v_j)$ such that $v_1,\ldots v_j$ have been visited. Then we have $$\tag1F(j,j)=\min\{F(i,j)+w(i,j)\mid 1\le i<j\}$$ and ...


3

You may find the following reference useful: Sciriha, Irene. "A characterization of singular graphs." Electronic Journal of Linear Algebra 16.1 (2007): 38. It describes necessary and sufficient conditions for the adjacency matrix of a simple graph to be singular (non-invertible). Be forewarned: these do not appear to be particularly "nice" conditions.


3

You will indeed use the pigeonhole principle: if $n = km + 1$ objects are distributed among $m$ boxes, then the pigeonhole principle asserts that one of the box will contain at least $k + 1$ objects. To expand a bit about my comment, you can even actually use the result for $6$ vertices an $2$ colors, to solve for $17$ vertices and $3$ colors. The simpler ...


2

It looks like you're looking for something related to Circulant Graphs. Below is a link: http://mathworld.wolfram.com/CirculantGraph.html Graphs in this class are parameterized by certain "jump" amounts. They're essentially like generalized petersen graphs except the "spokes" are contracted.


2

As far as I know, there is no "simple" necessary and sufficient condition of $G$ for an invertible adjacency matrix. A few comments: A necessary condition that generalizes your "each vertex needs at least one connection" condition is that if $S$ is any subset of vertices of the graph, there are at least $|S|$ vertices in the graph having at least one ...


2

For a unary function $S: P\to P$, the only wide subposets of $P$ in which $S$ is still monotone are those made with following rule: if you remove an arrow from $P$, you must remove the corresponding arrow(s) from $S^{-1}(P)$. In your example, the preimage of the arrow $1 \to 2$ via $S$ is the arrow $0 \to 1$. So when you remove $1 \to 2$, $S$ remains montone ...


2

Partial answer: That first formula does not work for counting directed graphs with prescribed degrees (I assume multiple edges and loops are allowed). One example where it fails is if $d^{out} = (2, 2, 0)$ and $d^{in} = (1, 1, 2)$. In this case, the formula gives $3$ but there are $4$ such graphs. To see the problem, consider trying to count the ...


1

Hint Prove first the following Lemma: Lemma: If $G$ is a graph where every vertex has degree at least 2, then $G$ contains a cycle. This Lemma implies that your graph has a vertex of degree at most 1. Erase this vertex for the inductive step.


1

We show that by recurrence on $n$ that: $$(A\oplus E)^{\otimes n}=\bigoplus_{k=0}^n A^{\otimes k}$$ $n=0$ $$(A\oplus E)^{\otimes 0}=E=\bigoplus_{k=0}^0 A^{\otimes k}$$ Assume the rpoperty to be true for $n$: $$(A\oplus E)^{\otimes n+1}=(A\oplus E)\otimes (A\oplus E)^{\otimes n}=(A\oplus E)\otimes\bigoplus_{k=0}^n A^{\otimes k}$$ $$= ...


1

Given a large connected graph, by definition it's number of edges are maximized when it is complete, in this case, every complete graph with $n$ vertices has $n-1$ connections. Consider a disconnected graph with several mutually exclusive connected subgraphs. It's a natural extension that the maximal number of edges for this graph will be when all it's ...


1

Let $A$ be the adjacency matrix of $\Gamma$. The Hoffman polynomial of your graph is \begin{align} p(x)&= \frac{12}{(5-\sqrt{5})(5-(-1))(5-(-\sqrt{5})}(x-\sqrt{5})(x-(-1))(x-(-\sqrt{5}) \\&= \frac{1}{10}(x^2-5)(x+1).\end{align} The main point here is that $p(x)$ is such that $P(A)=J$, where $J$ is the $12\times 12$ matrix with every entry equal to ...


1

You’ve made a pretty good start. You’re right that an $n$-cycle has $n$ spanning trees. Another way to explain it is to notice that deleting one edge leaves $n$ vertices and $n-1$ edges, so you have a tree; clearly that tree spans the cycle, and there are $n$ possible edges to remove, so there are $n$ spanning trees. With $K_4$, the tetrahedron, you got $4$ ...


1

Can we consider the following example: $G=(V,E)$ with $V=\{1,2,3\}$, $E=\{(1,2),(2,3),(1,3)\}$ and root designated to $1$, in which there is no cycle but $3$ is visited more than twice.


1

Its possible graph may be that :


1

Your proof is absolutely correct. If $v\ge 3$ then a planar graph must satisfy $e\le 3v-6$ (where $v$ is the number of vertices and $e$ is the number of edges).


1

From each vertex go out $r$ edges, but this way we count twice each edge, so the number of edges is $$m=\frac {rn}2$$


1

That image looks a lot like a book embedding of a graph. To project the book embedding onto the plane, you have to choose for each edge whether it should go above or below the central axis - assuming that is the axis is drawn horizontally.


1

It’s sufficient to consider connected graphs. First note that $G$ has at least $2$ non-cut vertices and therefore at most $n-2$ cut vertices. Next, let $\mathscr{B}$ be the set blocks of $G$. Let $\operatorname{bt}(G)$ be the graph whose vertex set is $\mathscr{B}$ and that has an edge $B_0B_1$ if and only if blocks $B_0$ and $B_1$ have a vertex in common. ...


1

Hint: Using the definitions of a walk, path and trial, we can figure out what exactly it is that you must find A trail is a walk where no edges are repeated. So we must thus find a walk between vertices 1 and 3 in which edges ARE repeated. A path is a walk in which no vertices are repeated. We must thus find a trail (a walk in which no edges are ...


1

The solution to this problem uses a clever application of Theorem 1.3.3 (in "The Probabilistic Method, 3rd edition"). Since not everyone has access to the text, I will state the theorem (with necessary definitions) here first. Definition: Let $\mathcal{F}=\{(A_{i}, B_{i})\}_{i=1}^{h}$ be a family of pairs of subsets of an arbitrary base set. $\mathcal{F}$ ...


1

Suppose S is a set not in F. If we can legally add S to F then we do. If we can't legally add S to F then there exists some T in F such that S and T are disjoint (or disjunct as you say). If that is the case, what can we say about the relationship between T and S's compliment? If you can show that you can add S's compliment to F instead of S then you ...


1

The definition used on the website you link to isn't the greatest one. In fact, I think it's incorrect as stated. The Tutte matrix is skew-symmetric, but that doesn't follow from the definition given there. The image used there comes from Wikipedia page on the Tutte matrix, where it is stated explicitly that it is skew-symmetric, but then, using their ...


1

This essentially amounts to finding the minimum number of edges a connected subgraph of $K_n$ can have; this is your 'boundary' case. The 'smallest' connected subgraphs of $K_n$ are trees, with $n - 1$ edges. Since $K_n$ has ${n \choose 2} = \frac{n(n-1)}{2}$ edges, you'll need to remove ${n \choose 2} - (n - 2)$ edges. If you remove strictly fewer edges, ...



Only top voted, non community-wiki answers of a minimum length are eligible