# Tag Info

0

$K_{3,5}$ with one edge removed.

0

Hint: A self-complementary graph on $n$ nodes has how many edges? If $G$ has $g$ nodes and $K$ has $k$ nodes, then how many nodes and edges does $G\times K$ have?

0

I doubt that this is the intended solution, but you can find min-cost paths in the presence of negative cycles using minimum-weight perfect matching. For the given graph $G$ construct a graph $G'$ such that \begin{align} V(G') &= \Big\{w_{\{u^3,v^0\}}, w_{\{u^2,v^1\}}, w_{\{u^1,v^2\}}, w_{\{u^0,v^3\}}\ \Big|\ \{u,v\} \in E(G)\Big\}, \\ E(G') &= ...

1

Let $G$ be a graph with chromatic number $k$ then $k = \min \{n\in \mathbb{N}\mid P(G,n) \neq 0\}$ where $P(G,n)$ is the chromatic polynomial. If when we contract the edge $uv$ the chromatic polynomial increases by more than one, then $P(G/uv,k+1) = 0$. From $P(G-uv,k+1) = P(G/uv,k+1) + P(G,k+1)$ it follows that $P(G-uv,k+1) = P(G,k+1)$, in other words, the ...

3

Suppose edge $v_1v_2$ is contracted to $v_3$ and $v_1$ originally connected to set of vertices $S_1$, $v_2$ originally connected to $S_2$. When $v_1v_2$ is contracted $v_3$ is connected to $S_1 \cup S_2$ and nothing other than $\{v_3\}\cup S_1 \cup S_2$ has changed connectivity. So if we give $v_3$ a new color that was not originally in the graph, it will ...

1

I would say no. I have to go give a class now but I think the proof would be something like this: Take a valid coloring of the initial graph, contract an edge between vertices $v_0$ and $v_1$ and give the vertex which results from merging $v_0$ and $v_1$ the color $v_0$ had in the initial coloring. If this coloring is not valid, then there has to be a ...

0

Graphic Sequence is only for simple graphs. It means that if a degree sequence is also a graphic sequence, the graph is simple. If you prove that a huge graph is a simple graph (using Havel & Hakimi) you can use the properties of simple graphs to select best algorithms to solve further problems on mentioned graph.

0

EDITED: Take an integer $M \ge 9$ such that you think there is an optimal solution with largest number at most $M$. Define boolean variables $x(i,j)$, where $x(i,j)$ is to be $1$ if node $i$ is assigned integer $j$, otherwise $0$. The constraint $\sum_{j=0}^{M} x(i,j) = 1$ implies that each node $i$ is assigned one integer. The constraint $\sum_{i=1}^{10} ... 2 Given a permutation$\pi$of a finite set$V$, form its cycle graph$G$as follows: the vertex set is$V$and the edges are pairs$(v,w)$for which$\pi(v)=w$. (This is a simple directed graph.) The adjacency matrix will in fact be the permutation matrix corresponding to$\pi$, which is invertible. We can also form graphs with loops whose adjacency matrices ... 0 From an algorithmic point of view, it's usual to think about where you place new vertices, not how you move them. Imagine that the UI allowed you to select a vertex, and click on a new position for it. This would make it clearer that the important thing is which side of a set of lines a vertex lies. For an even clearer way of looking at it, consider the ... 0 No. Let$G$be the disjoint union of$H_1=C_5$and$H_2=P_5$. Every edge of$G$belongs to exactly one of the$H_i$and the$H_i$have the same number of vertices, but not the same number of edges. 0 Hint: Let$f : V \to \mathbb{N}$be defined as $$f(v) = \sum_{u \in V \text{ is adjacent to } v} \deg(u),$$ and prove that the average value of$f$over$V$is at least$\frac{4m^2}{n^2}$. Solution: I hope this helps$\ddot\smile$0 This question is still unanswered. I'll write the outline of a solution. Rewrite$T_n$as a sum of weighted graphs$T_{i,j}$,$i < j$, where$(i,j) \in K_n$and$T_{i,j}$contains the (weighted) edges of the path from$i$to$j$in$T_n$. In each of the summands, the weight of a given edge$(i,j)$is$\frac{1}{paths(i,j)}$where$paths_{n}(i,j)$denotes ... 1 You can prove by contradiction. Assume all vertices in a graph$H$have different degrees. This means that$d(v_1)=0, \ d(v_{2n}) = 2n-1$. This is a contradiction, hence$H$can't exist. 0 Never mind: Mousset, Nenadov and Steger (arXiv:1312.1143v3) showed that$S_n(k) = 2^{(1-1/k)n^2/2 + o(n^2/(k+1))}$, even when$k$is a slowly growing function of$n$. This extends a result of Erdős, Kleitman and Rothschild from 1976 (preprint) for fixed$k$. 0 Take one vertex$n_1$out of$G$. The remaining graph$G'$is connected. Then take another vertex$n_2$that was originally connected to$n_1$out of$G'$. (1) If the remaining$G''$is connected, then we are good. (2) If the remaining$G''$has$m$components, we know all those components were originally connected with$n_2$. (<1> and <2> are ... 0 Let$G$be our 2-connected graph. Then$G$is 2-edge-connected as well(!). Take any minimal separating edge set$T$.$G-T$has exactly two components(!). These two components determine the vertices for$A$and$B$. The parts with (!) may need additional proof if you do not know them. 0 with compass and ruler. -use whatever method you are comfortable with to construct a pentagon. -draw lines from each corner, for a total of 5 lines, to the middle of the edge line connecting the next 2 angles of the pentagon. -set your compass to the length of the edge lines (incidentally this was the same size as the circles I used in ... 1 For a vertex partition$A,B$of$V$, and a vertex$v\in V$, let$t(v)$be the "cross-degree" of$v$, i.e. the number of neighbours of$v$in the other partition. Let$A,B$be a partition of the vertices of$G$, that maximizes$\sum_v t(v)$. Suppose$v\in A$has 2 neighbours in$A$, say$x$and$y$, and (at most) one neighbour,$z$in$B$. Then moving$v$to ... -1 Question >>> 1. How many triangles are there in the picture? Answer: $$2 \cdot (n - 2) -1 + 2 \cdot (n - 3) - 1 + \dots + 2 \cdot (n - n)] -1 =$$ $$= 2 \cdot [(n - 2) + (n - 3) + \dots + (n - n)] - n - 2$$ In our case, n = 8, then: $$2\cdot (6 + 5 + 4 + 3 + 2 + 1) - 6 = 36$$ n - 1$ 2 \cdot (n - 2) - 1 = 11 $triangles ... 2 Peterson graph can be defined as follows: It is a graph$G(V,E)$in which V is the set of all 2-element subsets of$S = \{1,2,3,4,5\}$and there is an edge$uv \in E$if and only if$u$and$v$are disjoint. Thus, there is no cycle of length 3, because it implies having at least 6 different elements in$S$. Note that every 2 nonadjacent vertices have ... 1 One way to show that the Petersen Graph has no cycles of length$3$is by examining its spectra. The eigenvalues of$\mathcal{P}$are$3^{1}$,$(1)^{5}, (-2)^{4}$, where the exponents denote their multiplicities. Note that$\sum_{i=1}^{n} \lambda_{i}^{3}$counts three times the number of triangles in a graph$G$of order$n$. So we observe that$3^{3} + ...

0

There are $k^{2}$ potential edges in a graph on $k$ vertices. We enumerate the graphs by selecting edges from the set of $k^{2}$ pairs. The number of selections is given by: $$\sum_{i=0}^{k^{2}} \binom{k^{2}}{i} = 2^{k^{2}}$$ So there are $2^{k^{2}}$ such directed graphs.

0

I'm aware of Chaco which is an open-source graph partitioning package written in C language. Chaco can do KL as well as many other partitioning heuristics. You can download it from http://www3.cs.stonybrook.edu/~algorith/implement/chaco/implement.shtml And user's guide is here https://cfwebprod.sandia.gov/cfdocs/CompResearch/docs/guide.pdf

1

If you need to traverse all leaves in a rooted tree with $E$ edges starting from the root and ending in this root then it will cost you $2 \cdot E$ (it doesn't depend on the traversal you choose, right?). If you stop at some leaf $n$ because you've already visited all other leaves then it'll cost you $2 \cdot E - depth(n)$. So, to minimize the cost you need ...

3

Let's suppose that these students go to Hypercube10 Highschool. In Mathematica, school = Graph[GraphData[{"Hypercube", 10}]] -- it's a graph with 1024 vertices and each vertex connects to 10 others. We can get distances between 100000 random pairs of students. data = Sort[Tally[Table[GraphDistance[school, RandomInteger[{1, 1024}], RandomInteger[{1, ...

1

In most cases the order you visit the subtrees does not matter, so you can avoid the combinatorial explosion. As an example, suppose the root has six branches, each the root of a subtree. Your optimal path will start at the far end of one subtree, come down to the root, cover four more subtrees returning to the root, and finally cover the last subtree ...

1

Every vertex in the graph can serve as the end point or an intermediate point in a $6$-path. If it's an intermediate point, this will cost it $2$ degrees; otherwise, only $1$ degree will be cost since an end point in a path has only degree one. This observation results in the following fact: Every vertex in a $5$-regular graph, must be an end point of at ...

4

Your 'multiset of integers' or signature is generally called 'degree sequence'. Your question is about graphs and multigraphs realizing certain degree sequences. Quite a lot has been researched and written about this. Ad 1: A necessary and sufficient condition is that the sum of all entries is even (@Henry's comment made me realize that this is only correct ...

0

You strategy for the first tree is a good one. As soon as you omit an edge from the center cycle, you are left with a tree. There are four possible edges you could omit. For the second tree, you might consider two cases: vertex $E$ either has degree one or degree two. If $E$ has degree one, we must choose one of its two incident edges to include in our ...

3

You must mean non-self-intersecting paths, otherwise the answer would be infinite. So: given a starting vertex $a$, and an ending vertex $b$, you can choose any subset of $k$ of the remaining $n-2$ vertices, and use them as intermediate vertices of a path in whatever order you like. So the answer is $$\sum_{k=0}^{n-2} \binom{n-2}{k}k!,$$ which is (an ...

0

To prove (b) let $v_0$ be any vertex. Since $\deg v_0\ge 2$, there is a vertex $v_1$ such that $\{v_0,v_1\}$ is an edge of $G$. Similarly, there is a vertex $v_2$ different from both $v_0$ and $v_1$ such that $\{v_1,v_2\}$ is an edge of $G$. Keep going: given $v_{k-1}$ and $v_k$, there is a $v_{k+1}$ different from both $v_{k-1}$ and $v_k$ such that ...

0

a) Trees are minimally connected, meaning the deletion of any edge disconnects the graph (into two nontrivial trees unless your graph is very special). By strong induction, these two trees each have at least two leaves. What can you conclude about the original tree? b) Since every vertex has degree at least two, you could consider a subgraph wherein every ...

1

The first inequality is correct: given an embedding for $G$ with a number of crossings, you can use the same embedding for $S$ by removing edges, which doesn't increase the number of crossings. However, I don't understand how you count the number of copies of $S$ in $G$. If you count all copies, then your claim is incorrect. For example, $cr(K_5)=1$ and ...

1

Yes what you said its true - given a graph $G$ its a hamiltonian path is a spanning tree of $G$ and not every spanning tree of $G$ is a hamiltonian path. With respect to what you say later on, we do have efficient algorithms for counting the number of spanning trees not finding all of them. Indeed the number of spanning trees is in general an exponential ...

3

My answer to your previous question works just as well for this one ($G$ has diameter $2$ and its complement has diameter $3$).

2

Let $\kappa$ be a cardinal number, and let $G=L(K_\kappa)$ be the line graph of a complete graph of order $\kappa.$ If $\kappa\gt4$ then both $G$ and its complement $\bar G$ have diameter $2.$

1

Yes. The Rado graph $R$ is a countably infinite graph with diameter $2$ whose complement also has diameter $2$. The Rado graph is characterized by extension properties: Given any two finite disjoint subsets $A$ and $B$ of $R$, there is a vertex $v$ in $R$ such that $v$ is adjacent to every vertex in $A$ and $v$ is not adjacent to every vertex in $B$. Given ...

2

There are two nice introductions. First, as I mentioned in comments, it is Introduction to Random Graphs, a recent book on the classical theory of random graphs, which presupposes much milder prerequisites than, e.g., Bollobas' classic. (The book is not sold yet, but you can find a draft on one of the authors' webpages) I also very much like the monumental ...

1

I just noticed I didn't post my answer. Better late than never. Apologies. The following answer is based on user264781's insight. Let $b\in\mathbb{N}$. Let $C_{b\left \lfloor{\sqrt{n}}\right \rfloor}$ be a circle with $b\left \lfloor{\sqrt{n}}\right \rfloor$ vertices. For $1 \le k \le \left \lfloor{\sqrt{n}}\right \rfloor$, there are $b\left ... 0 Recall that projection operator$\,P\,$acting from a vector space$\,U\,$to its subspace$\,V,\,$spanned by orthogonal vectors$\,\vec{v}_{1},\, \ldots,\, \vec{v}_{k},\,$can be represented as a matrix composed of column vectors$\,\vec{v}_{1},\, \ldots,\, \vec{v}_{k}multiplied by its transpose: \begin{align} P:U\to V, \qquad \forall\; \vec{x} \in U ... 0 Not in general. However, for particular values ofn$, you sometimes get some coincidences. For example, if$n=7$,$F(1,3)=F(2,4)=840.$For$n\le 100$, the only values of$n$for which any value$F(i,j)$occurs more than four times are $${7, 15, 17, 19, 27, 31, 32, 34, 38, 47, 49, 55, 59, 71, 76, 77, 79, 87, 97};$$ in none of these cases does any$F(i,j)$... 1 This sort of problem can be solved using the linearity of expectation. The average degree can be not only estimated but given exactly. I interpret your notation to mean that$n$vertices are independently uniformly distributed in the unit square and two vertices are joined by an edge if their distance is$\le r$. Then a given vertex$v$at least distance ... 2 I'm studying random geometric graphs (RGG's) in the context of ad-hoc wireless networks. I am not sure that I can help you but I will tell you what I know. Erdos-Renyi (or Bernoulli) random graphs are one example of a random graph but there are many others. Indeed, since the probability that a distinct pair of vertices share an edge is the same for all such ... 0 You need to divide by 2 because the order of the two graphs doesn't matter. For example, you decompose into subgraphs$A$and$B$; it is the same as if you decompose into$B$and$A$. The best way to think of it is by colorings; you want to color all the edges using red and blue. But if you consider the red and blue edges as separate subgraphs and ignore ... 0 If$n\geq3k$then$1+2\lceil\frac k{n-2k}\rceil\leq 1+2=3$, so the statement is obviously true. For$n\leq 2k$there are no cycles at all, so we may restrict ourselves to$n=2k+t$where$0<t<k$. Assume$v_1,\ldots,v_{2m+1}$is an odd cycle. The$k$elements of$v_2$must be completely different from those of$v_1$and$v_3$has at least$k-t$... 0 An example is given by a transitive tournament, i.e. for$n\geq 2$you have vertices$v_1,\ldots,v_n$and you create edge$v_iv_j$if and only if$j>i$. Then for each$i$the indegree of$v_{i}$is$i-1$and the outdegree is$n-i$, so both indegree and outdegree are different for different vertices. Example: for$n=4$we have vertices$v_1,v_2,v_3,v_4$... 0 Below is the proof replicated from the book by Narsingh Deo, which I myself do not completely realize, but putting it here for reference and also in hope that someone will help me understand it completely. Things in red are what I am not able to understand. Proof Let the number of vertices in each of the$k$components of a graph G be$n_1,n_2,...,n_k\$. ...

1

As you said, functions define relations between the different "dimensions" of the space. This idea is made explicit via correlation functions in Gaussian processes (this is an excellent non-engineering introduction) which can be framed in the theory of Reproducing Hilbert Kernel Spaces (RHKS). Based on your comment, I think you might want to look at the ...

1

You have certainly identified an error in the paper. In your diagram above the set Z would be the 11 edges: AB, BC, CA, AX, AY, XY, BX, BY, CC1, CC2 and C1C2 (because you can only count XY once). So each layer would have at most 31 edges outside Z giving a max total of 11 + 3x31 = 104, not 102 as he states in the paper. But his argument still works ...

Top 50 recent answers are included