New answers tagged

2

Brinkmann graph has chromatic number 4 and girth 5 (so it has no cycles of length 3 or 4) See https://en.wikipedia.org/wiki/Brinkmann_graph Other such graphs: Foster Cage : http://mathworld.wolfram.com/FosterCage.html Wells graph (again on MathWorld, but I can't post the link...) EDIT, by the way, it has been proved (I think Erdos among the others) ...


0

I am not sure if there is a way to assign weights to nodes. Perhaps you can replace each node by an edge with negative weight according to its desirability. Also you can have positive weights on the rest of the edges as usual. Now the problem reduces to the known problem of finding shortest path (least total weight). Algorithms such as Dijkstra or ...


0

Suppose you have $n$ rows and $m$ columns. Create $n$ nodes name $R_i$ to represent each row. Each row can have at most 1 white square, so add 1 edge entering $R_i$ with a capacity of $1$. If Table entry $T_{i,j}$ is white, add it to the graph. Connect an edge from $R_i$ to $T_{i,j}$ with a capacity $1$. This represents "The row has chosen this cell". ...


1

The graph doesn't exist since you need the vertex of degree 5 to be connected to all the others (in particular both vertices of degree 1 already have their single neighbor). Now the vertex of degree 4 must be connected to 3 of the vertices with the following degrees: 3,2,1,1. In particular it must be connected to a vertex of degree 1. This is a ...


1

My interpretation: The Confusion arises, here- Assume that both $X$ and $X'$ have $n$ vertices. We plan to code the graph labels as suitable subgraphs which we attach to the vertices of $X$ and of $X'$. In time polynomial in the length of the input we can rename the labels and may assume, therefore, that $L = \{1 ..... k\}$ is the set of labels ...


0

Thanks for the answers. I have found a solution at least to get my graph completed so far, the example above is just to demonstrate what my problem was. I decided to create junctions with the lines that all narrow down to just one line I guess it is a mathmatically legal move in the context of what I originally stated because the lines only touch, not ...


2

"a polynomial time reduction from the colored graph isomorphism to the regular graph isomorphism" .... the below proof is due to Pascal Schweitzer, Theorem 1 (reduction of colored to uncolored graph isomorphism). The graph isomorphism problem for colored graphs polynomial-time reduces to the uncolored graph isomorphism problem. ...


1

Draw this graph without vertex 10 or 15. Then think of constricting the path 4-20-5-30 down to a single vertex. Remember, you don't need to have $K_{5}$ or $K_{3,3}$ as subgraphs, only a subgraph that is a subdivision of $K_{5}$ or $K_{3,3}$.


0

The terminology can vary, but it is usual to talk about a labelling of a graph for the most general case. Although labels can be text strings, they are usually numbers. These labels can also be referred to as colors although this usually has a more precise meaning. For example, from the graph coloring wikipedia: When used without any qualification, a ...


2

You can't do it without trickery. This is known as the three utilities problem and the graph you are trying to draw is $K_{3,3}$ which is known to be non-planar. The types of trickery used are to draw the graph on a torus or to say they are pipelines and one can go over another.


1

First fix the image of $x_0$. There are three possibilities. Since the edge $[x_0,x_1]$ gets mapped to one of the edges connected to the image of $x_0$, you have two choices: you either move clockwise or counter-clockwise. The necessarily also fixes $x_1$. Repeat this decision 20 times, once for each edge. So you have $$ \underbrace{3}_{\text{Number ...


0

@ vrume21: Assuming, by the tags and some other hints on your question, that the kind of network you are talking about is related to the classical definition of "graph" (non-empty collection of vertices together with a subset of the relation of the cartesian product of the vertices, meaning, the set of connected vertices), and by some definitions in ...


1

Wikipedia has a listing of open problems in graph theory.


1

A graph with least eigenvalue at least $-1$ is a disjoint union of cliques. (Proof: the least eigenvalue of $K_{1,2}$ is $-\sqrt2$, interlacing.) The graphs with least eigenvalue at least $-2$ were characterized by Cameron, Goethals and Seidel. They are line graphs, so-called generalized line graphs, and a finite set of graphs associated to $E_6$, $E_7$, ...


2

Here are a few that I know of (with overlap of course). It's unclear how up-to-date they are. Douglas West's page: http://www.math.illinois.edu/~dwest/openp/ The Open Problem Garden: http://www.openproblemgarden.org/category/graph_theory Erdos' Problems on Graphs: http://www.math.ucsd.edu/~erdosproblems/


1

HINT: If $G$ has more than two components, pick vertices $u$ and $v$ in different components. Say that these components have $n_u$ and $n_v$ vertices, respectively. What is the maximum possible value of $\deg u+\deg v$ in terms of $n_u$ and $n_v$? How does $n_u+n_v$ compare with $n$?


1

Every two vertex of a circuit are connected by two different, non-overlapping paths. If we take only one edge out, then we are destroying one of those paths. This, we can still reroute paths which involved getting through 2 vertex of the circuit via the other path.


1

Hint: If the path from $v$ to $w$ does not contain $e$, we are done. If it does contain $e$, then the path is $v\ldots a b\ldots w$, where $e$ is an edge from $a$ to $b$. But $a$ and $b$ are in a circuit. What does that tell you about the number of ways to get from $a$ to $b$?


1

As mentioned in the comments above, the statement you are likely expected to prove is that $\Delta(G)\color{red}{\leq}6$, not $\Delta(G)=6$. Suppose for purposes of contradiction that $\Delta(G)>6$. Then there is some vertex $v$ where $\deg(v)\geq 7$. Without loss of generality, let $\deg(v)$ specifically be $\deg(v)=7$. Then, there will be exactly ...


0

Consider the graphs on numbered vertices. When $p=1/2$, every graph is equiprobable, so the probability to get a a particular graph is $1/2^{n \choose 2}$. Now if you want some isomorphism class $G$ (a graph on undistinguished vertices) you just erase the labels, which gives you a factor of $aut(G)$, the number of automorphisms of $G$.


2

If they had the same edge set, they would be the same graph. We could have $E=E'$, but in general this is not the case. The edge set consists of pairs of vertices, and there's no reason for $E$ and $E'$ to have the same pairs. $\tau:X\to X'$ is an isomorphism and $\kappa^{-1}:X'\to X$ is an isomorphism. Composing them gives an isomorphism $X\to X$, which is ...


2

An explanation(Not a proof): Let, $F_1$ and $F_2$ are 2 copies of $G$. Keep first $i$ vertices fixed in both $F_1$ and $F_2$. You do not need to overthink gadgets, it is not essential to understand the proof, it is required for implementation. Just consider that first $i$ vertices are fixed. By definition, $H_{i+1} \leq H_{i}$, and $H_i$ is a group of ...


1

Let $G$ be a triangle with vertices $x,y$, and $z$ and edge weights $1$ for $xy$, $2$ for $yz$, and $4$ for $xz$. Take $x$ as source. The shortest path from $x$ to $z$ in $G$ is $xyz$, with weight $3$, but if you add $2$ to each of the weights, the shortest path from $x$ to $z$ is $xz$, with weight $6$. The shortest path from $x$ to $y$ does not change: it ...


1

Take the 16 elements of the Galois field $\mathbb F_{16}$ as vertices and color the edge connecting $i$ to $j$ with the class of $i-j$ in $\mathbb F_{16}^\times/\mathbb F_{16}^{\times 3}$. Since there are 5 cubes in the field, there are 3 classes in this quotient. Working this out with Mathematica gives me this coloring table for the edges: 1 3 2 ...


1

In case that you need a complete proof, see the following article. Singleton, Robert R. (1968), "There is no irregular Moore graph", American Mathematical Monthly 75 (1): 42–43


0

Considering you are looking Binary trees with $n$ nodes, I think $2n!/((n+1)!*n!)$ is the answer (Catalan numbers). But if you are looking for trees (not specifically binary) with $n$ nodes then the answer is $n^n/n^2$ by Cayley's formula.


4

Depends on your definition, but if you define bipartite as two-colorable or having no odd cycles, then the empty graph or the trivial graph are the minimal bipartite graphs.


1

If by "smallest" you mean "number of vertices", then that is one possible answer. But you could also remove the edge to leave two vertices and no edges, and perhaps you will consider this to be "smaller" than your example.


1

We first prove $R(4,3)\leq 9$. In other words, if $K_9$ is colored red and blue there is a red $K_4$ or a blue $K_3$. Pick a vertex $v$, it has $8$ edges coming out. Suppose $6$ of them are red, then the $K_6$ on those six vertices contains a red $K_3$ or a blue $K_3$, if there is a red $K_3$ we get a red $K_4$ after adding vertex $v$. Suppose $4$ of them ...


2

you don't need that result(actually usually that result is proved USING the fact that maximal planer graphs have only triangular regions!) To prove your result, observe that it isn't true for $n=1$ and $n=2$ so let $n\geq 3$. Assume to the contrary that there is a maximal planar graph $G=(V,E)$ embedded in the plane with a region that is not a triangle. ...


1

Take a region which is not a triangle. What is your definition of region? Can you add an edge? Hope that helps,


3

The question is likely asking you to prove that at most one of $G$ and $\overline{G}$ is bipartite. If a bipartite graph $G$ has order 5 or more, by the pigeonhole principle one of the "parts" has at least 3 vertices. This means that $\overline{G}$ has $K_3$ as a subgraph, so $\overline{G}$ is not bipartite.


5

I'm pretty sure the question is to prove that at most, one of $G$ and the complement of $G$ are bipartite (at least if that's what you denote by $\overline G$).


0

Let $C$ be a $2$-CNF formula. We prove that if $C$ is unsatisfiable then there is some variable $x$ such that $x$ is reachable from $\bar x$ and vice versa in the implication graph $G(C)$. The proof uses induction on the number $n$ of variables in $C$. Base case. If $n = 1$ then $C$ must contain clauses $x \vee x$ and $\bar x \vee \bar x$ and hence the ...


0

The answer is no. Your $k_i$ parameters are not enough to reconstruct the graph, and not enough to count triangles in the complementary graph (which is what $K_n$ represents). For example, consider $P=\{\{1,2\},\{2,5\}\}$ and $Q=\{\{1,3\},\{1,4\},\{2,5\}\}$. They have the same $k_i$ parameters, namely $2,1,0,0,0$. However the first one has five triangles ...


0

The implication graph tells you that 'if $x$ is false, then $y$ has to be true' to make some litteral true, and therefore the formula true. So if you have a bicycle, it means that you have a sequence of implications that say that for some $w_i$, $w_i$ has to be true and false to satisfy the formula. Since this is a contradiction the formula is unsatisfiable. ...


1

There is. Suppose the number of boxes of each size is respectively $x_1, x_2, x_3, \cdots, x_k$. Then the number of boxes visible is the largest of these numbers. Proof: We cannot nest any box in a smaller box. In a larger box, exactly one such box fits. In short, in each visible box is at most one box of a given size So the number of boxes visible is at ...


1

Create a digraph $G=(V,A)$ as follows: $V=S_k$: so one node per element of the multi set $S_k$ Create an arc from $u$ to $v$ if and only if $u<v$ You are now looking for a minimum number of paths that cover your graph $G$. Since $G$ has a transitive structure, you can use the Dilworth Theorem to answer your question (in polynomial time). It will give ...


0

There are $2$ possibilities for each of the $k$ coordinates of a vertex, so there are $2^k$ vertices in total. Each vertex has $k$ neighbours (why?) so the sum of the degrees of all the vertices is $k2^k$. But this counts each edge twice, so... To show that the graph is bipartite, consider the coordinate sum of a vertex. If this sum is even, what can you ...


0

Given the complete graph $K_n$, it is clear that $\alpha(K_n)=1$ as any two vertices are adjacent and thus any set with more than one vertex is not independent. Similarly, any subset of less than $n-1$ vertices cannot be a vertex cover, as it would not include an edge in the graph, so $\tau(K_n)=n-1$. So the formula is valid: $$\alpha(K_n) + \tau(K_n) = 1 + ...


0

Assuming I've understood the question correctly, here's a counterexample:


0

You will not be able to show that one of the induced subgraphs "is Rado"; that is false, because the late Dr. Richard Rado was a man and not a graph. The best you can hope to prove is that one of those induced subgraphs is a Rado graph. In order to answer the question in a way that will be helpful to you, I would need to know which definition or ...


1

A set of columns of the incidence matrix are linearly independent if and only the corresponding edges form an acyclic graph. The rows and columns of the adjacency matrix are indexed by vertices.


2

If you had a polynomial-time algorithm (with a known polynomial complexity bound, say $C n^p$) to find an isomorphism for a pair of graphs that are in fact isomorphic, you could use that to determine in polynomial time whether two graphs are isomorphic. Namely, you run the algorithm with a time limit of $C n^p$, and check whether it produces an isomorphism. ...


4

Putting identical gadgets on the vertices in each copy means you add some characteristic so that, in an isomorphism from one copy to the other, you force a particular vertex to get mapped to a specific other vertex. For example, say we have two copies of $K_{5}$, vertices labelled identically $1,2,3,4,5$, and I want an isomorphism fixing $1$. Then in ...


2

As other commenters have pointed out, there is no simple algorithm for all graphs that runs very fast. I know that 'very fast' is vague, but I'm not able to discuss the complexity of the problem particularly well. However... For many classes of graph - such as those of bounded degree, treewidth, etc - there are various algorithms to determine an ...


0

Try reading Mathon's paper (pages 1 - 2): http://www.sciencedirect.com/science/article/pii/0020019079900048 It should be explained there more clearly.


10

This a very interesting question which I am afraid has (as of the moment) a somewhat disappointing answer. The problem of graph isomorphism has been an object of study of Computational Complexity since the beginnings of the field. It is clearly a problem belonging to NP, that is, the class of problems for which the answers can be easily verified given a ...


1

Consider $G=K_n-e$, the complete graph on $n$ vertices minus one edge $e=[u,v]$. This graph $G$ is an interval graph, and its only (and of course minimal) separator consists of $n-2$ vertices that separate $u$ from $v$.


1

You need to add a lot more detail and clean up some inaccuracies. First, the negation of the conclusion isn’t that $G$ is not connected by a unique simple path: it’s that there are two vertices, $u$ and $v$, of $G$ that are not connected by a unique simple path. We’re assuming that $G$ is connected, so $u$ and $v$ are connected by at least one simple path; ...



Top 50 recent answers are included