Tag Info

New answers tagged

0

The number of such digraphs is $(n-1)^n$, because each vertex chooses one out of the other $n-1$ vertices to be at the end of that directed edge. In random graphs, the graph chosen at uniformly at random among all such digraphs is called $D_{1-out}$. I'm not sure if this collection of graphs goes by another name.


0

We assume $G$ has more than $k$ vertices and is $k$-connected. To say that a graph $G$ is $k$-connected means that we can remove any $k-1$ vertices from $G$ and still have a connected graph. So, to show that our new graph $H=G+w$ is $k$-connected also, we have to show that $H-V_{k-1}$ is still a connected graph, where $V_{k-1}$ represents a vertex-cut-set ...


0

1) What you have computed is the total degree, not the average degree. 2), 3) The example you have given has 3 leaves. If you still think the answer to 2) is 2 leaves, you should provide another example.


3

Technically, $C_n$ will have $n$ spanning trees ($n$ choices for the edge you you delete). But they are all isomorphic (paths of length $n-1$), so it depends on whether you want to consider them as distinct or the same.


0

To ease up notation let's put $n = 2k + 1$, and remember that $n$ is odd. The vertices of $Q_n$ are all the $2^n$ strings of zeroes and ones. Two types of such vertices go in $H$ : those that have $\lfloor \frac{n}{2} \rfloor$ zeroes and $\lceil \frac{n}{2} \rceil$ ones, or vice-versa. Focus on the former. In how many ways can you have $\lfloor ...


0

What about this algorithm: While there are still edges in our graph{ Sort L by vertex degree (number of edges on the vertex). Let v = Maximum of L; Add v to K. Delete all vertices (and their incident edges) that are adjacent to v. Delete v from L. }


1

Consider the following operation: We first choose a set $T$ of $\ell$ vertices of $H$ uniformly at random. We then choose a $k$ vertex subset $S$ of $T$ uniformly at random. If we ignore $T$ entirely, the resulting distribution on $S$ is uniform. In particular, the probability that the vertices of $S$ induce $G$ is $d_G(H)$. On the other hand, we can use ...


0

The answer is straight forward when you let $H_1$ be a cube which has $8$ vertices and it is $3$-regular and let $H_2$ be a $3$-regular graph with $8$ vertices that contains four triangles. Sure, $H_1$ and $H_2$ are not isomorphic. Meanwhile, to construct $H_2$, two triangles each will share a common base on two sides of $H_2$ while the tops of these ...


-1

The answer would just be the complete graph on $n$ vertices. There is a single edge between any two vertices which are not equal. This is just the definition of a complete graph.


1

You can't do very much. Note that the complete bipartite graph $K_{n,n}$ has average degree $n$ yet it is 2-colorable. I think the "best" bound of this type that one could possibly obtain is by using the inequality $$\chi(G) \leq \frac{1}{2} + \sqrt{2m+\frac{1}{4}},$$ holding for a graph with $m$ edges.


1

Observe that graph eigenvalues are algebraic integers. Prove that algebraic integers that are rational must be integers.


1

The partially ordered set is the set of trees such that every edge lies on a path in that tree between two elements of $U$. The ordering is by inclusion. It satisfies the upper bound property because if we have a chain of such trees, we can take the union of their edges. This is a tree because any loop is a finite collection of edges and those edges will ...


1

Hint: How many edges does a spanning tree on $2014$ vertices have? How many edges are in $C_{2014}$? I don't know what a bipartite graph has to do with this.


0

I want to help with this so much, but the poor notation, grammar, and markup are making it impossible to figure out what exactly you are asking for. Please proofread your question for clarity and use this to type your mathematics. What does this mean? ..., ∀u∈L, ∃ s= {ei(u,wi)} ∈E; i=1,2.....n connect u to wi, where w∈R Typeset nicely as best as I can ...


1

The article you linked to deals with the asymmetric travelling salesman problem. The authors have a subsequent paper which deals with the more usual symmetric TSP: Gutin and Yeo, "The Greedy Algorithm for the Symmetric TSP" (2007). An explicit construction of a graph on which "the greedy algorithm produces the unique worst tour" is given in the proof of ...


2

A possibility is to start with a huge $3$-regular graph $G_{2n}$ with $2n$ vertices then joining couples of vertices with degree $3$ (the degree of any vertex in such a couple goes from $3$ to $4$) with an edge. Each time we add an edge, the dominating eigenvalue eigenvalue slowly increases, going from $3$ to $4$ (if we add $n$ edges, we get a $4$-regular ...


2

Yes. Choose one vertex. It has sixteen edges going out, so six of some color, say yellow. Now consider the $K_6$ composed of those six vertices. If it has no yellow edges, it has two monochromatic triangles and we are done. If it has two yellow edges, we have two monochromatic triangles and are again done. If it has only one yellow edge we have one ...


0

You may have a look at the paper "A Primer on Galois Connections" by Erné et al. (see the preprint here), where an antitone Galois connection from $\mathcal{P}(X)$ to $\mathcal{P}(Y)$ is called a polarity. You will find therein many examples and references, including the link with formal concept analysis. However it does not deal specifically with the case ...


0

Let $X$ be a vertex of degree $x$. Let $P_y$ be a shortest path from $X$ to a vertex of degree $y$ and $P_z$ be a shortest path from $X$ to a vertex of degree $z$. If $P_y$ uses a vertex of degree $z$, or $P_z$ uses a vertex of degree $y$, then we've found the required path. So we can assume that $P_y=(X,X_1,\ldots,X_k,Y)$ for vertices $X_i$, each of ...


0

What you are describing is a subset of automated planning. You would typically describe your problem in an action language like STRIPS and then run a planner to determine whether the goal state or states can be reached. Determining whether a successful plan exists for a given problem is PSPACE-complete, but constraints such as limiting the number of steps ...


0

Perhaps I'm overinterpreting the example and its presentation in the Question, but if the problem is determining all simple (no retracing edges) paths in an undirected cycle-free connected graph, i.e. a tree, there is a simple Answer. Given there are $n$ nodes in the tree, any pair of (not necessarily distinct) nodes uniquely determines a simple path ...


3

I'm assuming that $\Delta$ is the maximum degree, and $\bar{G}$ is the complementary graph. If $G$ has three connected components, then the (or one of the) smallest one has cardinality less or equal to $n/3$, so the sum of the number of nodes in the other two is $2n/3$ or greater. That means that exists a node in the smallest component connected to at ...


0

This is called a minimum path cover, optimal path cover, or path partition. The number of paths in a minimum path cover is the path covering number. This paper gives quite an extensive list of references on the problem: http://arxiv.org/pdf/1204.2306.pdf


1

Hint: prove that $u$ and $v$ have a common neighbour. Detailed hint: Assume $u$ and $v$ have no common neighbour. Let $N(x)$ be the set of neighbours of $x$. Then $|N(u)\cup N(v)|=deg(u)+deg(v)$. But what is the maximal $N(u)\cup N(v)$?


1

You know that for a tree it holds $$\sum_{v\in V} d(v) = 2|E| = 2(|V|-1) $$ Now you know that there are $|V|-(33+25+15)$ vertices of degree $4$ and therefore: $$ 33\cdot 1 + 25 \cdot 2 + 15\cdot 3 + [|V|-73]\cdot 4 = 2|V| - 2$$ Now just find the value of $|V|$.


1

I doubt if what you have presented can be called a proof. We can discuss that in the comments. For a proof choose a maximal path $P$ in the graph. (I am assuming the graph is finite.) Let $v$ be an end point of $P$. Now since $\delta(G)\geq 2$, there is an edge $e=vx$ incident to $v$ such that $e\notin E(P)$. But since $P$ was a maximal path, the vertex ...


0

Hint: start from a generic vertex $v$. Its degree is positive, so there is some neighbor $w$ which has another neighbor other than $v$. We keep going along this path finding new vertices. Then we reach some vertex, say $z$, which doesn't have a new neighbor. But it's degree is at least two. What does that tell us?


0

But by handshaking lemma, we know that the minimun number of edges required to draw a graph is sum of degrees of vertices/2. In this case also this is happening as sum of degrees of vertces=even. Then also still why we can not have such a graph possible?


0

Case $1$: "$G$ is connected" Assume that $G$ does not contain a cycle. Then $G$ is a tree. We know that every tree contains at least $2$ leaves, that is, vertices of degree $1$. However, this is a contradiction since $\delta(G)\geq2$. Thus $G$ contains a cycle. Case $2$: " $G$ is disconnected" Assume that $G$ does not contain a cycle. Then $G$ is a forest ...


1

If every vertex has degree at least $2$, then depth-first search can always proceed until it finds a vertex that is active. The active vertices at that moment form a cycle.


0

The 'either' here is ambiguous, and I hate it when they do this. For some, "either A or B" means just "A or B" (at least one, but it could be both). For others, "either A or B" means "A exclusive-or B" (at least one, but not both). So the minimum would be to prove that at least one of the two holds. Actually in this case, it's and exclusive-or, so let's ...


1

If $T$ is a spanning tree of your graph $G$, it is easy to see that the shortest walk of $G$ is at worst as big as the shortest walk of $T$. Therefore, the worst possible shortest walks are found on trees. Say your walk of a tree $T$ has to start from $r$. You can root a given tree arbitrarily, so assign $r$ as the root. Suppose $r$ has at least 2 ...


1

To prove that a star is the worst case, it is perhaps best to look at a spanning tree $T$. Choose any leaf $v$. By induction, you can visit all the vertices of $T - v$ in $2(n-1) - 3$ steps. Along the way, you can visit $v$ in two steps. So you can visit all of $T$ in $2(n-1) - 3 + 2 = 2n - 3$ steps.


0

No such graph exists: If such a connected graph existed, that joined all vertices(nodes), it would need to have atleast $8$ edges. This means the total degree would need to be $\geq 16$. Here we have a total degree of $14$, which isn't possible. Even without the $8$ edge observation, we have $4$ vertices with degree $1$, this means the remaining degree ...


0

Suppose such a graph G exists. Then G can not contain a cycle. For, then all the vertices must be of degree 2 or there must be a vertex of degree at least 3 as G is connected. Thus, we are looking for a connected acyclic graph, that is a tree, with 9 vertices and 7 edges. But every tree with 9 vertices must have exactly 8 edges. So such a graph G doesn't ...


2

First, why the claim is true. Take any vertex. If it's matches to the same vertex in both perfect matching, then it had degree zero on the symmetric difference. Otherwise it has degree two. Second, after removing all isolated vertices in the symmetric difference, all vertices have degree two. Take any such vertex and follow its two edges. What you get is a ...


0

Consider the graph G associated with the triangulation $\tau$ where the vertices in G correspond the faces of the triangles in the triangulation, and two vertices of G are connected by an edge if the two corresponding faces of the triangulation share a common edge. So you can see this problem as a 2-coloring problem. Let v be a interior vertex of $A$, in ...


0

This isn't exactly what you are looking for but it is similar. Frankl defines an $\textbf{oriented k-uniform hypergraph}$ as an pair of vertices and edges, where each edge is a $k$-tuple of distinct vertices with the following extra condition: for any subset of size $k$, at most 1 of the possible $k!$ edges consisting of these vertices is actually present. ...


1

a) is false. Consider $C_n$, the cycle of length $n$ for $n\geq 5$. Note $C_n$ is $2$-regular (and triangle free), so $\Delta(C_n)=2$. Hence, there can be no vertex with degree $$\geq \frac{n}{2}\geq\frac {5}{2}=2.5.$$


2

Look at everything modulo $2$. The matrix $A^l$ is singular, and so for some $v$, $Av=0$. This gives the second property. The first one follows from $A^lv=0$.


0

"(ordered) tuples, rather than subsets"... That would still be a hypergraph. Your representation would have hyperedges be the result of some function $f$ with domain $H$, and codomain in, say for example, the set of nondecreasing sequences. For example, the hyperedge $\{2, 6, 1, 6, 7 \}$ would be represented in your system as $(1, 2, 6, 6, 7)$. Usually some ...


0

Let $H$ be a connected graph and let $G$ consist of $n$ copies of $H$. The point group $\Gamma(G)$ contains elements that map each copy of $H$ to itself. Thus, the $n$-fold direct product $\Gamma(H)^n$ is a subgroup of $\Gamma(G)$. Also, the different copies of $H$ can be permuted amongst themselves, giving another $n!$ automorphisms $S_n$. These two ...


1

According to my calculations in sage, there are 16 4-regular graphs on 9 vertices, of which only one is planar. The planar graph is the line graph of the complement of $C_6$, and it is not self-complementary.


2

Here is a source for a construction: S.B. Rao, On regular and strongly-regular self-complementary graphs. Discrete Mathematics 54 (1985), pp. 73–82. See Theorem 2.3. This solution seems to answer a more specific question, so it's likely that there is a simpler answer to your question, which I would be interested in.


0

If you want a systematic approach, I'd recommend the Havel-Hakimi algorithm. Start out with all the vertices you want labeled with their desired degrees. Then choose the vertex that needs the most edges (say $d$), and connect it to the $d$ other vertices that need the most edges. Everytime a vertex receives an incident edge, lower the desired degree by ...


6

Color four vertices of the cube together with the ants sitting there blue, and color the other four vertices together with the ants sitting there red, as shown in the following figure: Let $V_b$ be the set of blue vertices. Each blue ant marches from its vertex to one of the red vertices, but not to the red vertex opposite to the starting vertex. ...


1

Yes, they are the same. For a quick explanation, I'll paraphrase Hatcher's discussion from his book Algebraic Topology. In terms of CW complexes, a graph is a space $X$ obtained from a discrete set $X^0$ be adding a collection of 1-cells $e_\alpha$. In non-CW speak, this means $X$ is formed from the disjoint union of $X^0$ with closed intervals $I_\alpha$ ...


0

Hint: write out the definition of the Laplacian matrix of $G$. By multiplying the matrices, figure out what the $ij$-entry of $MM^T$ is. Does this match up with the $ij$-entry of the Laplacian?


0

The nodes that violate the strong triadic closure property are B,E, and F


0

Assume one of them is bipartite. So, at least one of parts has 3 or more vertices. Let's pick 3 of them and call them u, v, w. As these 3 vertices are in the same part, they have no connection. Therefore, in the complement graph there are uv, uw and vw edges. Now, u, v, w, u is a cycle of length 3 and it shows that complement graph could not be bipartite.



Top 50 recent answers are included