Tag Info

New answers tagged

2

Not necessary, consider the directed graph on $A,B,C,B',C'$ with arcs $A\to B$, $B\to C$, $A\to C$, $A\to B'$, $B'\to C'$, and $A\to C'$. This directed graph is a counterexample to your claim since $A\to B$ and $A\to B'$ do not lead to a common vertex. P.S. Combinatoric is not a word, combinatorial is.


0

For $m,n\in\mathbb{N}$, $\text{Aut}\left(K_n\right)\cong S_n$ and, if $m \neq n$, $\text{Aut}\left(K_{m,n}\right) \cong S_m\times S_n$, whereas $\text{Aut}\left(K_{n,n}\right)\cong C_2\times S_n^2$, where $C_k$ and $S_k$ are the cyclic group of order $k$ and the symmetric group on $k$ elements, respectively. If your complexity is the size of the ...


0

First of all, a diagram in $\mathcal{C}$ is not the same thing as a directed graph. A $\Gamma$-shaped diagram in $\mathcal{C}$ is a morphism of graphs $\Gamma\longrightarrow U(\mathcal{C})$, where $U(\mathcal{C})$ denotes the underlying directed graph of $\mathcal{C}$ ${}^{1)}$. Secondly, it makes sense to talk about commutativity for all kinds of graphs. ...


0

gt6989b's comment goes most of the way towards solving your problem. The number of paths from $i$ to $j$ of length $m$ is $(X^m)_{ij}$, so the number of paths from $i$ to $j$ of length at most $m$ is $\left(\sum_{k=0}^mX^k\right)_{ij}$. In your case, all these entries should be positive for $m=5$, so you want $$ ...


1

Solution follows, stop reading if you want to figure it out yourself. Order nodes so that the leaf comes first and its neighbour comes next. Claim. $1, 1, -1, -1$ cannot be balanced. Proof. Suppose that in step $0$ we have the above and in step $n$, where $n$ is minimal, we have $0, 0, 0, 0$. In step $n-2$ we must have $a, -a, a, -a$ (or the last two ...


1

If it is a finite graph, the answer is yes, because for fixed $n$ there is only a finite number of paths of length $n$ in the graph. For example, you can enumerate all $n$-tuples of distinct vertices in the graph, check whether they form a path, compute the hash value of that path if they do, and check if that hash occurs in your list of hashes.


0

There is an old principle in combinatorics. To count the number of sheep in your field, count the number of legs and then divide by four, the number of legs per sheep. Look at the expression $$\frac{(2n)!}{2^n n!}.$$ Here $(2n)!$ is the number of permutations of your set of $2n$ things. Given such a permutation, can you think of a simple way of getting a ...


0

Let $f(n)=\frac{(2n)!}{n!2^n}$. The idea is to proceed by induction on $n$, the base case being trivial. So suppose that $f(n-1)$ is the number of perfect matchings on a complete graph with $2(n-1)$ vertices. Consider a complete graph on $2n$ vertices and fix a vertex $v$. Any matching $M$ of this $K_{2n}$ contains an edge $e$ incident to $v$, say ...


1

I drew UG and added six more isolated vertices. Now, in G' K6 is a subgraph and therefore G' is nonplanar.


0

In this problem, I shall assume that $G$ is a simple graph. There are counterexamples if $G$ is not simple. Indeed, there is a counterexample for any given number of vertices (consider any star graph and replace every edge by a pair of parallel edges). Hint: If $G \cong G^*$, how many edges does $G$ have as a function of the number of faces? What is the ...


0

A clique of a graph is a subset of the vertices with the property that each vertex of this subset is adjacent to every other vertex of the subset (complete induced subgraph)


0

Your understanding of clique is correct. However the maximal clique in that graph is {1,2,3} and not {1,2,3,4,5}. {1,2,3,4,5} is not even a clique in that graph.


1

Partial answer: If $n$ is prime, then every vertex-transitive graph with $n$ vertices is isomorphic to one of the form that you have given, because every transitive permutation group of prime degree $p$ contains a $p$-cycle. In general, the property that divides the vertex-transitive graphs into these two classes is whether the automorphism group of the ...


0

As JMoritz noted : I would think that the graph with adjacencies defined as $v_i$ is adjacent to $v_j$ with $j=((−1+i+n) \ mod \ 200)+1,$ $n∈\{−3,−2,−1,1,2,3\}$. (I.e. $v_4$ is adjacent to each of $v_1,v_2,v_3,v_5,v_6,v_7$ whereas $v_1$ is adjacent to $v_{198},v_{199},v_{200},v_2,v_3,v_4$). Each vertex has exactly 6 edges, and you can check that it is in ...


1

There are many books for graph theory, and you should select the topics that suit the education goals of the course. For example, in computer science the Graph theory algorithms is highly considered as main topic in each graph theory course. Personally, I prefer the following two books: Introduction to Graph Theory Graph Theory (Graduate Texts in ...


0

You can not do it. The sum of the degrees need to be an even number! Can you prove this?


0

For combinatorics, I would highly recommend the book by Yao Zhang. Its an excellent wealth of information and provides common strategies for counting that tackle pretty much all problems out there. It has both text that teaches you, example problems, and "challenge" problems. You can find it easily online.


0

Not sure I am clear on your proof. it is not true that removing a minimal valence node from a cycle keeps the graph connected: think of a "benzene molecule", a graph consisting of a cycle and one node hanging off each cycle node. To prove the statement you want: choose a node P at random. For any node V define L(V) to be the length of a minimal path ...


1

No. You misunderstood the definition of 2-connected. This says that you can't remove a vertex such that the graph becomes unconnected. You have merely proven that there exists a vertex that can be removed such that the graph remains connected. The claim is not true either. For this, consider the 3-path.


-2

By a well known theorem of Erdös, the smallest non-trivial asymmetric graphs have V(G)=6. The Reconstruction Conjecture states that all finite graphs with 3 vertices or more are vertex reconstructible. So the vertex reconstructability of nontrivial, finite asymmetric graphs is entirely contingent on this fundamental, and yet unproved, result. The question of ...


3

You might call it a vertex-signed graph. See e.g. this paper.


1

Hint: Can you describe a weighted finite graph by a string unambiguously (that is, each string corresponds to at most one graph)? If so, the set of weighted finite graphs is countable.


1

For the incidence Hopf algebras arising out of graphs the author in the article http://www.dmtcs.org/pdfpapers/dmAO0146.pdf gives a formula. For general incidence Hopf algebras one can look at http://home.gwu.edu/~wschmitt/papers/iha.pdf for the antipode formula.


0

Let $K$ be the aforementioned group of Hamiltonian cycles. It has size $H+1$, where $H$ is the number of Hamiltonian cycles. Let $J$ be the group of $S\subset \mathscr{P}(\text{faces})$ under symmetric difference. I'll formalise your idea about each Hamiltonian cycle $h$ being sent to a set $f(h)$ of faces monomorphically by $f:J \to K$, then, noting that ...


1

This proof works for finite graphs only. Suppose contrary that, for every $v\in V$, there exists an edge $e_v=\left\{v,w_v\right\}$, where $w_v\in V$, such that $e_v$ is not a part of any maximum matching in $G$. Let $M$ be a maximum matching in $G$. Since $G$ has no perfect matchings, there is a vertex $v\in V$ not matched in $M$. Note that $w_v$ has ...


1

I think you can prove it just fine using the language of graph theory. Case 1. Suppose that $n_k \leq \frac{n}{2}$. For simplicity, let's index all the vertices in $V$ so that vertices of $X_1$ are first, then vertices of $X_2$ and so on, i.e., take arbitrary bijection $f : \{0,1,\ldots,n-1\} \to V$ such that \begin{align} X_1 &= ...


1

Sorry, I erased my previous answer because it had too many problems (why I shouldn't do math so late at night). There are really two things to say: if the symmetric difference of a collection of faces is again a cycle, or even a union of disjoint cycles, then there is nothing to show; it is two regular, so clearly has an eigenvalue equal to $2$. But is ...


0

Looking at the building structure as an array, with each element position being its floor, each number assigned to it the floor number of the 2nd building it has a zipline connected to, or 0 if there's no zipline. With this simple python code: def validZipline(zipline): for i in range(len(zipline)): for j in range(i): if zipline[j] ...


1

Check out the formulas given in this equivalent StackOverflow question. http://stackoverflow.com/questions/27086195/linear-index-upper-triangular-matrix


3

A consequence of Turan's theorem: If a graph, $G$, is traingle free, then $|E(G)| \le n^2/4$ where $n$ is the order of the graph. Translating this to our specific case, we have that $E(G)=n^2 \le \frac{(2n)^2}{4}=n^2$. Thus, our graph has the maximum number of edges to be triangle free, and so it is the Turan graph $T(2n,2)=K_{n,n}.$ Therefore, it is ...


1

Hint: bipartiteness is equivalent to having no odd cycles.


1

Hints: Let $f_i$ denote the number of faces of degree $i$. Then you have $f=f_3+f_4$ and $2e=3f_3+4f_4$ (counting edges along the boundary of each face counts each edge twice). Now play with these equations, the $2v=e$ that you know, and Euler's formula to calculate $f_3$. For the second part, you now know the value of $f_3$. If it is the case that every ...


1

This continues to be part of the research I'm doing on graph coloring. If one relaxes the condition of "minimum degree $5$" to "$4$-connected" (that is, the triangulation $T$ must be $4$-connected rather than minimum degree $5$) but insists that the graph still be $4$-connected after an edge joining vertices of at least degree 5 is deleted to form a ...


1

The problem is equivalent to having $r$ piles: pile $1$, pile $2$, pile $3\dots$ pile $r$ with $n_1\leq n_2\leq \dots \leq n_r$ coins respectively, and allowing the following operation: selecting two non-empty piles and removing a coin for each. The number of vertices in the maximum matching is therefore equal to the maximum number of coins we can remove ...


2

Since the outer face must have length 4 or 6, it should be possible to prove your graphs must be at least 3-connected. But then your graphs are examples of Barnette graphs (cubic bipartite 3-connected planar graphs) which are conjectured to all have Hamiltonian cycles. These have been studied fairly extensively, and you can find a drawings of all the ...


3

It sounds like you're right ! Suppose that $C$ is a minimal edge cut that yields at least 3 components. Call $G'$ the graph obtained after removing $C$ from $G$. Put back any edge $e \in C$ in $G'$. The two endpoints of $e$ belong to at most 2 of the components, so adding $e$ can only reduce the number of components of $G'$ by one. In other words, $G' ...


0

As I understand it, a minimal cut set is one where no subset is also a cut set. If that's the case then I don't see how you can have three components connected by a minimal set. Here's my reasoning. First, connect the three components with two edges. Then you can delete either edge and get a pair of components. Now, connect them with three or more (N) ...


1

There isn't necessarily a single term that satisfies all of your criteria under all discussions. https://en.wikipedia.org/wiki/Rooted_graph Rooted DAG (directed acyclic graph), often (almost always) has the condition that the graph is reachable from the root vertex (you would technically qualify that the first time in a paper if you wanted to be formal). ...


0

You can use the definition of simplical vertices. A simplical vertex $v$ is a vertex whose neighbors $N(v)$ form a clique. Thus, the set of vertices $V =\{v\} \cup N(v)$ is the set that you are interested in.


0

Another classical network model is Small World networks by Watts and Strogatz. You can have a look at their seminal paper here


0

I think that the authors means "without". They wanted to test the modularity measure in networks where there is no community structure, i.e, for random structure of the networks.


0

Let's first formulate Pavel's idea in terms of the Bondy–Chvátal theorem instead of Ore's Theorem. The theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian, where the closure is defined as the unique graph resulting from successively adding edges between any pair $u,v$ of vertices with $d(u)+d(v)\ge n$. So a non-Hamiltonian ...


1

Hint: Let $v$ be a vertex, and let $w_1, w_2, \ldots, w_k$ be the vertices it is connected to, in clockwise order. Because all faces are triangles, $w_1$ must be connected to $w_2$, and $w_3$ must be connected to $w_4$, and so on, with $w_k$ connected to $w_1$. If the three colors are red, yellow, and blue, let $v$ be red and $w_1$ be blue, WLOG. What must ...


1

Gerhard Koester in 1985 constructed infinitely many planar 4-regular graphs that not only are 4-chromatic, but also 4-critical, that is, all their proper subgraphs are 3-colorable. The only planar 3-regular 4-critical graphs is the complete graph of order 4, by Brooks's Theorem. Curiously it is known that no 5-regular planar graph is 4-critical. But I am ...


-1

It is not a correct definition of a simple graph. A pair $(a,b)$ is different from the pair $(b,a)$, but a simple graph does not have two edges with the same ends. It is not incorrect, but maybe unusual, to disallow empty and infinite vertex sets. It would be a correct definition of a non-empty finite directed graph, in which case each arc (edge) has an ...


0

Actually, it's ambiguous what you want exactly. However, I tried to write some Matlab code (I am not the best in programming, but I tried since to no answers): clc;clear;close k = 6; x = 1:k; T1 = 100 * rand(1,k); % creating 6 random T1 - values T2 = 50 *rand(1,k); % creating 6 random T2 - values hold on plot(x,T1,'-o') plot(x,T2,'-*r') %% ...


0

The case $s=1$ with $n=k^2$ students given $k+1$ homework assigments in groups of $k$ is directly related to the problem of finding $k-1$ mutually orthogonal Latin squares of order $k$. From $m$ homework assignments to $k$ groups of $k$ students each, we can construct $m-2$ mutually orthogonal Latin squares of order $k$. Let $a_{ij}$ be the number of the ...


1

The solution you suggest in your third edit isn't rigorous, since $\left|S\right|=(n-2)p$ is just an approximation; the actual number of edges emanating from $v$ varies. (It's also not clear how "given $v$ and $u$" is to be interpreted, given that $u$ was introduced in an existential clause referring to the vertices being counted.) The probability that a ...


3

The number of spanning trees in the complete graph $K_n$ with a degree $d_i$ specified for each vertex $i$ can be counted using Prüfer codes. The Prüfer code has $n-2$ slots, of which $d_i-1$ contain the label $i$, so the number of Prüfer codes corresponding to the specified degrees is the multinomial coefficient $$ ...


3

We can use some group theory to count the number of cycles of the graph $K_k$ with $n$ vertices. First note that the symmetric group $S_k$ acts on the complete graph by permuting its vertices. It's clear that you can send any $n$-cycle to any other $n$-cycle via this action, so we say that $S_k$ acts transitively on the $n$-cycles. The orbit-stabilizer ...



Top 50 recent answers are included