Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

0
votes
0answers
4 views

Coloring chordal graphs

It is well-known that the graph coloring problem --- given a graph $G$ and a number $k\in\mathbb{N}$ decide whether $\chi(X)\le k$ --- is NP-complete. However, certain classes of graphs can be colored ...
1
vote
0answers
8 views

Definition of a minimal set of automorphisms generating an orbit?

By definition, the orbit of a vertex v in a graph G is the set of all vertices f (v) such that f is an automorphism of G. I wonder whether there is a definition for a minimal set S of automorphisms ...
1
vote
1answer
26 views

Topological structure/graph from a paper

This question is based off a paper titled "On designing heteroclinic networks from graphs." I'm having a difficult time visualizing something "drawn in 4-dimensions" projected down to a 2-dimensional ...
2
votes
1answer
14 views

What's the name of an 'extended' cycle graph

I'm looking for the name of a regular cycle graph, where each node is connected with it's k neighbors. In particular, I'm looking for a lemma at Wolfram Mathworld or Wikipedia. An examples of this ...
1
vote
1answer
16 views

Prove number of edges in an edge-disjoint spanning tree

I have the following problem. It isn't homework--it's additional work I want to do to further grasp the material in my Combinatorics class. Show that if a graph $G$ contains $k$ edge-disjoint ...
-2
votes
0answers
31 views

Why are Cayley graphs of $SL_2(\mathbb{F}_p)$ defined in this peculiar way?

Naively it would have been natural to pick the symmetric group of generators from members of $SL_2(\mathbb{F}_p)$ but instead one defines a set $S_p$ which is a "natural projection modulo $p$" of an ...
1
vote
0answers
27 views

The graph has an Euler tour iff in-degree($v$)=out-degree($v$)

I am looking at the proof that $G$ has an Euler tour iff in-degree($v$)=out-degree($v$), that I found at this site: www.cs.duke.edu/courses/fall09/cps230/hws/hw3/headsol.pdf (Problem 2) A simple ...
-9
votes
1answer
63 views

Theory of 4 colors [on hold]

Je pense que j'ai pu trouver une contre-exemple, sur la conjecture des 4-couleurs!, Veuillez voir ca: http://cjoint.com/?EDyoaOVaS3S @@@ I think I could find a cons-example, 4-color conjecture !, ...
0
votes
0answers
17 views

Determine the value of $ex(n,P_4)$

I want to determine the exact value of $ex(n,P_4)$ I believe that the answer to this is $n$, if $n\equiv 0$ (mod $3$), and $n-1$ otherwise. Given n vertices, one can create multiples of $K_3$. If ...
0
votes
0answers
14 views

Probabilistic proof for expander existence

I am new to probabilistic proofs and trying to understand them better. Apparently, a common probabilistic proof focuses on the existence of expanders (eg. vertex expanders). I've been using the search ...
1
vote
1answer
78 views

A math contest question related to Ramsey numbers

In a group of 17 nations, any two nations are either mutual friends, mutual enemies, or neutral to each other. Show that there is a subgroup of 3 or more nations such that any two nations in the ...
2
votes
0answers
41 views

Card layouts and graph theory

I define a layout of cards to be the placement of each card arbitrarily in three dimensions, observed from a particular angle. Cards cannot be bent, folded, cut or mutilated in any way. Every layout ...
1
vote
0answers
30 views

Is there a method to measure the similarity between undirected graph vertices?

I'm doing some research on User Identity Resolution. Assume i can get two undirected graphs of a person, one is the friendship in Twitter of that person, the other ...
0
votes
0answers
8 views

Are there any minimum-degree-5 triangulations of the sphere for which every four-coloring consists of six Kempe chains, one for each color-pair?

I'm interested only in triangulations that have no separating triangles (i.e. triangles for which there are vertices both inside and outside the triangle). The 5-regular icosahedron is one. Are ...
0
votes
1answer
18 views

Hamilton-like paths in digraph

We are given digraph with two (possibly the same) vertices - let's call them S and F. We are also given some set of vertices W (possibly empty, possibly consisting of all vertices of digraph). We ...
1
vote
0answers
14 views

Task about Hartley information(logarithm from cardinality of the set) of a number of paths in a graph and about limit linked with this information.

Let $L_n$ be the number of all paths of length n in a directed graph(below). It is needed to find $lim_{n \to \infty}\chi(L_n)/n$ where $\chi(L_n)$ is Hartley information in $L_n$ set. (If I am not ...
1
vote
1answer
29 views

Number of labeled graphs satisfying a degree sequence

Say we have two sequences of integers $d^\text{in}$ and $d^\text{out}$ representing the in- and out-degree sequences of a directed graph. How many (possibly isomorphic) graphs are there that satisfy ...
0
votes
0answers
13 views

Petri Nets Elementary Circuit Algorithim

I'm lost as to how you tackle this question in the picture attached? Could someone please explain it in Lehman's terms or even just get me started? Thanks!
2
votes
0answers
50 views

Tree decomposition by hand for understanding

I am implementing "algorithm 2" from the paper "Treewidth computations I. Upper bounds" by Bodlander and Koster[1,page5] and I am not sure if I understand it or not. As I understand, the algoritm ...
1
vote
1answer
23 views

Let G be an r -regular graph with n vertices and m edges. Prove a simple algebraic relation between r , n, and m.

I know that it for any regular graph $r_{n}$ that we can show a relation between r, n, m. However, I'm not sure how to find or prove this relation. I assume that the relation will be something like ...
1
vote
0answers
41 views

Graph Combinatorics: How many such Graphs are there?

How many $4$-regular graphs exist on $8$ vertices? I found that such a graph can't be disconnectd since if so, then graph can be written as disjoint union of atleast two graphs. $4$ regularity ...
1
vote
0answers
19 views

Analogue of Fáry's theorem taking sphere and geodesics instead of plane and straight lines.

Fary's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments (see Wikipedia). The proof is based on the Art gallery theorem, so I ...
9
votes
1answer
178 views

Twilight Zelda Guardian Puzzle : Shortest Path Proof

I'm playing a video game right now and in it is a puzzle (see here). There are solutions to solving it (see here) on the Internet, but I'd like to know if this path is the shortest path (least amount ...
0
votes
1answer
24 views

Maximum Number of Vertices of a block-cutpoint graph

For a graph $G$ on $n \geq 1$ vertices, what is the maximum number of vertices of its block-cutpoint graph $BC(G)$? What I have so far: The block-cutpoint graph of a graph $G$ is the bipartite graph ...
5
votes
1answer
83 views

Two pawns walking in a complete graph

We have a complete graph $G = \langle V,E\rangle$ with non-negative values on edges. Let $C = \{v_1,v_2,\ldots,v_n\}$ be an ordered collection of $G$'s vertices. At the beginning we have two pawns in ...
0
votes
1answer
25 views

Counting spanning trees in labelled graphs

I have some troubles with counting spanning trees, it seems completely abstract to me. First one is cycle with n vertices - it's just n, because we can move each number n times like so: ...
-1
votes
1answer
105 views

Proving by induction on the number of vertices that: every acyclic simple graph is bipartite

Prove that every acyclic simple graph is bipartite, by the use of induction. I have quite some trouble with induction. Specifically, I know that acyclic graphs have at least one vertex that has a ...
2
votes
2answers
41 views

Give a formal argument why there is no planar graph with ten edges and seven regions. Here is my answer

I'm really new to a graph theory, and I have to answer the following question: give a formal argument why there is no planar graph with ten edges and seven regions. Here is my answer: Using ...
0
votes
0answers
45 views

Convex polyhedra with edges of equal length

This is again a natural category of polyhedra without having an own name. Is it possible, that their graphs are the same as the graphs of polyhedra with faces of regular polygons? My question is ...
0
votes
0answers
35 views

Calculate distance between known intersecting points

I have been working on this problem for awhile now and I think I just need a few fresh minds to help me out. I have 4 lines that intersect and form a shape. This is part of a much larger problem, ...
1
vote
1answer
74 views

Interesting Graph Theory “WOMVIES” problem

Here is an interesting problem: A graph is a set of vertices (points), some pairs of which are joined by an edge. For this problem, we will not allow an edge to join a vertex to itself (i.e., no ...
1
vote
0answers
17 views

Expected number of leaf nodes in some theoretical graph models

If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of: (A) a random graph (e.g., Erdos-Renyi graph), (B) a small-world graph ...
2
votes
1answer
44 views

Percolation over the integers

Imagine a simple undirected graph with a countably infinite number of vertices, each labeled with an unique integer $v \in \mathbb{Z}$. Connect the vertices by edges randomly such that Each vertex ...
0
votes
1answer
37 views

Tutte matrix - Determinant

I'm trying to understand the proof of the "magic theorem" about the Tutte matrix which states: Let $T$ be the Tutte matrix of $G(V, E)$. Then, $$\det(T) = 0 \quad\Longleftrightarrow\quad G ...
1
vote
0answers
25 views

question regarding edge space

Given a graph $G=(V,E)$ and it's edges space $\mathcal{E}(G)$ in the book by Diestel it defines given two edges sets $F,F'$ and their coefficients $\lambda_{1},...,\lambda_{m}$ and ...
0
votes
0answers
34 views

The number of edges in a tree is $n-1$

I am trying to prove that the number of edges in a tree is $n-1$ where $n$ is the number of vertices. I do not wish to use induction. I already have established that a tree is a planar graph. Now my ...
0
votes
1answer
17 views

Breaking connectedness by removing edges from the complete graph $K_n$

Given the complete graph on $n$ vertices $K_n$, what is the smallest number of edges you can remove in order to separate the graph into two disjoint subgraphs? I consider vertices without edges to be ...
0
votes
1answer
52 views

Does the graph exist with these degrees?

$(11,2,2,2,2,2,2,2,1)$ Is it possible that a degree of a vertex can be 11 ? However, there are only 9 vertices. Does the graph exist?
2
votes
0answers
21 views

Max cut problem

I've just looked at the standard proof using the probabilistic method stating that the max cut problem has a lower bound of $|E|/2$ for any graph $G=(V,E)$. More specifically if $X$ is the random ...
0
votes
1answer
13 views

What are existing methods to count colored subgraph frequencies in a large colored directed graph?

I have a directed colored large network or graph. By 'color' I mean that nodes are of different categories. There are some small 3 or 4 node colored directed subgraphs. I need to know how to count ...
0
votes
0answers
29 views

Vector multiplication with both subscript and superscript, in training algorithm for McCollugh-Pitts neurons?

Can someone here help me understand what's going on with the Vis, with both the subscript and superscript notation (as included in the images supplied below)? Is it Einstein Notation? I'm almost ...
0
votes
1answer
49 views

size of enclosed area in travelling salesman problem optimum

Can we say the size of enclosed area of optimum solution is greater than enclosed area of any other solution in a TSP problem?
0
votes
1answer
31 views

What is the walk of this graph?

A walk that is not a trail from vertex 1 to vertex 3; A trail that is not a path from vertex 1 to vertex 3; A path from vertex 1 to vertex 3. How can I describe these walks?
1
vote
1answer
46 views

Icosahedral Graph

Let $Γ$ be a graph cospectral with the icosahedral graph having spectrum $\{[5]^1,[\sqrt{5}]^3, [-1]^5,[-\sqrt{5}]^3\}$. I have shown that Γ has 12 vertices, 30 edges, regular with each vertex having ...
1
vote
1answer
22 views

The dual of transporting problem

So basically I'm trying to figure out what does a certain variable in dual of transporting problem mean. Transporting problem in matrix form: (We are searching for a min cost of transferring goods ...
1
vote
0answers
19 views

Co ordinate independent linear algebra over graphs

It is frequently said that Linear algebra is not correct until it is coordinate free or something to that effect and indeed, almost all the major results can be stated without picking a basis. ...
0
votes
1answer
13 views

Solving Through The Use Of Handshakes.

Let $G$ be a graph. Use the Handshake Theorem to prove that $\delta(G)\nu(G) \le 2\varepsilon(G) \le \Delta(G)\nu(G)$. So the first step to solve this I know is that you need to know what ...
0
votes
1answer
21 views

Condition to detect cycle in graph

Which of the following condition is sufficient to detect cycle in a directed graph? A. There is an edge from currently being visited node to an already visited node. B. There is an edge from ...
0
votes
0answers
8 views

Calculating the Estrada Centrality

The Estrada centrality of a node i is given by $E_i =(e^A)_{ii}$ where $A$ is an adjacency matrix Express the Estrada centrality in terms of the number of loops of length r $N^r_{ii}=[A^n]_{ii}$ ...
0
votes
1answer
57 views

What kind of tree it is? How to solve the problem?

I have a tree with following configuration: n is the number of different vertices v ($0 \lt v \le n$). Each vertice ...