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

25
votes
0answers
383 views

What is that thing that keeps showing in papers on different fields?

A few months ago, when I was studying strategies for the evaluation of functional programs, I found that the optimal algorithm uses something called Interaction Combinators, a graph system based on a ...
19
votes
0answers
554 views

Normalizers of automorphism groups

In abstract groups $\Gamma$ the normalizer $N_\Gamma(S)$ of a subset $S\subseteq\Gamma$ is the subgroup of all $x \in \Gamma$ that commute with $S$, i.e. $xS = Sx$, i.e. $x\ y\ x^{-1} \in S $ for all ...
13
votes
0answers
427 views

Analyzing a class of vertex-deletion games

As part of the discussion on this question (Permutation Game Redux), a simple vertex-deletion game was proposed. The game is very simple. Disconnect. Players alternately remove vertices from a ...
13
votes
0answers
904 views

A constrained topological sort?

Suppose that one has a directed, acyclic graph G, and each vertex $v$ contains a (positive) value $a_v$. Additionally, let $r$ be a constant. For my purposes, $r>1$, but this might not matter. ...
12
votes
0answers
125 views

What can we say about the graph when many eigenvalues of the Laplacian are equal to 1?

The Laplacian of the graph has all the eigenvalues real and non-negative, the smallest being 0. I have a graph where the second smallest eigenvalue (the so called algebraic connectivity) is equal to ...
11
votes
0answers
172 views

Dynamically two-coloring a finite graph

Let $G=(V,E)$ be a finite graph whose vertices are going to be colored dynamically. More precisely, consider time periods $t \in \left\{0,1,2\ldots,\right\}$ and for each time $t$ and $i \in V$, let ...
11
votes
0answers
208 views

Genus of the graph $K_{4,2,2,2}$.

What is the genus of the complete $4-$partite graph $K_{4,2,2,2}$? What i know: Since $K_{4,4,2}$ is a subgraph of $K_{4,2,2,2}$, and genus of $K_{4,4,2}$ is 2, $K_{4,2,2,2}$ has genus greater than ...
11
votes
0answers
607 views

Minimal time gossip problem

The gossip problem (telephone problem) is an information dissemination problem where each of $n$ nodes of a communication network has a unique piece of information that must be transmitted to all the ...
11
votes
0answers
301 views

“Semidirect product” of graphs?

The first subquestion is "has a standard notion of semidirect product been defined in graph theory"? If yes, i'd like to know if the definition i'm gonna give is equivalent to the standard one. I'd ...
10
votes
0answers
180 views

Quotient Groups and Covering Spaces in Painting Hanging

Consider the $1$-out-of-$n$ painting hanging problem: Given $n$ nails in a wall, how can we hang a painting such that upon removal of any nail, it falls. This has a nice interpretation as a problem in ...
10
votes
0answers
114 views

Who has a winning strategy in the hamilton-circle-game?

The game starts with a graph with $n$ vertices and no edges. The players alternately add edges until the graph contains a hamilton-circle. The player who made the last move loses. Who has a winning ...
10
votes
0answers
187 views

Reconstruction Conjecture and Partial 2-trees

Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old. Searching relevant ...
9
votes
0answers
239 views

Number of sets of vertices whose union of neighbours contains exactly $k$ vertices

Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows: For example, $g$ for $n=3$: If ...
9
votes
0answers
193 views

Branching processes and couplings

A text I am reading is discussing ways to couple branching processes, and describes the following 2 pairings, the latter of which I am failing to understand. (I include the former for the sake of ...
8
votes
0answers
281 views

Probability of the existence of a path of a specified length between any tw0 vertices in a random graph

Let $G$ be a graph with $n$ vertices, whose average degree is $k$. What is the probability that between any two vertices, there exists a path of length at most $l$? NOTE: For the above problem the ...
7
votes
0answers
258 views

How is graph theory used to solve problems in number theory?

What are some applications of graph theory in number theory? How can a graph theory approach be useful to solving number theory problems? In general, is graph theory ever useful in making number ...
7
votes
0answers
123 views

A connection between nonplanar complete graphs and the alternating group?

I went to an undergrad's senior honors thesis presentation a few days ago. She was discussing crossing numbers and mentioned that complete graphs $K_n$ are nonplanar iff $n \geq 5$. ?Coincidentally? ...
7
votes
0answers
398 views

Problem with an algorithm to $3$-colour the edges of cubic graphs

I'm currently trying to implement an algorithm to $3$-colour the edges of cubic graphs. (I want to do this with Matlab's Symbolic toolbox). After restricting to planar graphs to ensure the existence ...
6
votes
0answers
54 views

Heuristics for topological sort

I have a number of modules connected in a Directed Acyclic Graph. My problem is to find an optimal execution order (minimize the total execution time). Any topological sort suffices for a valid ...
6
votes
0answers
63 views

Game, stealing edges in a graph.

I was inventing a problem for a math contest, I was really pleased with it, but then I found a mistake in my solution and have not been able to solve it. It is as follows: Alice and Bob play a game. ...
6
votes
0answers
41 views

Chromatic Number of Circulant Graph

Consider the Circulant Graph $Ci_{2n}(1,n-1,n)$ as described here: http://mathworld.wolfram.com/MusicalGraph.html Another way to describe $Ci_{2n}(1,n-1,n)$ would be $2n$ vertices with vertex set ...
6
votes
0answers
81 views

Given $100$ coplanar points, no $3$ collinear, then at most $70$ percent triangles formed using these points are acute-angled

(IMO-$1970$) Given $100$ coplanar points, no $3$ collinear, prove that at most $70$ percent of the triangles formed using these points are acute-angled. I know that one solution proceeds by ...
6
votes
0answers
152 views

graph product that commutes with automorphism, and semi direct

Is there a way to construct a "product" of graphs $G\rtimes H$ such that $Aut(G \rtimes H ) \simeq Aut(G) \rtimes Aut(H) $? A related topic is "Semidirect product" of graphs? but not quite ...
6
votes
0answers
102 views

A game may related to graph theory or topology

Last Sunday, I played a game with a group of people. The game is as follows: A group of people form a circle as shown below: Each person must remember how he/she is linked with his two neighbours. ...
6
votes
0answers
95 views

When can an edge subset of a graph be extended to become an element of its cycle space?

Let $F$ be a set of edges in a graph $G$. Show that $F$ extends to an element of the cycle space of $G$ iff $F$ contains no odd cut. The context for this exercise is the following: Let $G = (V,E)$ be ...
6
votes
0answers
82 views

Maximum number of cyclic quadruplets in tournament

Consider a tournament with $n$ contestants - that is, a complete graph directed graph $K_n$ where each edge is pointed one way or the other. We call a subset $\{a,b,c\}$ a "cyclic triplet" if each of ...
6
votes
0answers
168 views

Traveling salesman problem: can a terrible strategy beat a good one?

Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
6
votes
0answers
133 views

Have these (extremely simple) classes of algebraic structures been considered in the literature? If so, what are they called?

Questions. Have the following kinds algebraic structures been considered in the abstract algebra literature etc.? If so, what are they really called? (I have used made-up terminology for the sake ...
6
votes
0answers
144 views

Parity of sum of Kronecker deltas in a graph

For some fixed $n\in\mathbb N$ let $G$ be a graph on the vertex set $\{1,\dots,n\}$ with a total number of $k$ edges $e_1,\dots, e_k$. For any vertex colouring $c(i)$ of the graph, $\delta_e$ is ...
6
votes
0answers
246 views

Probability of transmission between two nodes in a neural network at exactly d timesteps

I have a network which is an Erdős–Rényi graph. It is a simple neural network with degree 0.7N where N is the number of nodes. Each weight between neurons is 1/N, meaning that if node n has fired the ...
6
votes
0answers
117 views

Shortest closed loop containing all extreme points of a convex set

Suppose $S\subset \mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to\mathbb{R}^2$ is a continuous map with $\Gamma(0)=\Gamma(1)$. Suppose $\Gamma$ passes through all extreme points of $S$. ...
6
votes
0answers
182 views

Constructing a directed graph from its spectrum

This is related to the following question from cs theory stack exchange: http://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem So it seems as if given a sequence of real ...
6
votes
0answers
280 views

What can we say about two graphs if they have similar adjacency matrices?

Suppose we have two (finite, simple, undirected) graphs, what can we say about these graphs if they have similar adjacency matrices? Observations to begin with: If $G_1$ and $G_2$ are isomorphic, ...
6
votes
0answers
378 views

Slices of a hypercube

Take the unit $d$-cube with vertices $\{0,1\}^d$, and restrict to the vertices that lie between (or within one of) a pair of parallel hyperplanes. These vertices form a graph whose edges are the edges ...
6
votes
0answers
155 views

Combinatorial vs. geometric symmetries of graphs and their drawings

Associated with a graph $G$ and its automorphism group $\text{Aut}(G)$ (reflecting its combinatorial symmetries) are drawings in the plane with - eventually - one or more (geometric) symmetry groups. ...
6
votes
0answers
157 views

Unit Distance structure of Hoffman Singleton graph

This question has been bugging me since last 3 years. Prove or disprove that Hoffman Singleton is an unit distance graph in $\mathbb R^2$. For those who are new to unit distance graphs, A graph is ...
6
votes
0answers
216 views

Ramsey (graph) theory question with tree and girth

Sorry for the abundance of questions I'm asking. Test is soon... Prove that for every tree $T$ and every $g \in \mathbb{N}$, exist $G$ with girth $g$, so that in any 2-edge-coloring of $G$ there is a ...
6
votes
0answers
238 views

Edge Coloring of Kneser Graphs

Kneser graphs KG(n, k) are well known: vertices are all k-subsets of {1,2,...,n} with two sets connected iff they are disjoint. If the graph is odd (i.e., has an odd number of vertices) it is easy to ...
6
votes
0answers
195 views

What do we know about graph degree sequences?

The sequence of sizes of single vertex cuts of a graph is called its degree sequence. Is there an agreed-upon name for the sequence of sizes of k-vertex cuts? What can be said about two graphs which ...
6
votes
0answers
217 views

Determining graph minors quickly

I know very little graph theory. I am trying to determine if one graph, A, has as a minor another graph, B. I know the problem is slow in general, so I am looking for things that I might be able to ...
5
votes
0answers
31 views

Single loop polyhedra

The odd antiprisms are both Eulerian and polyhedral, with the first implying that the edge can be represented with a single closed path. The Cuboctahedron also has that property. With the rule to ...
5
votes
0answers
165 views

Mapping $\Delta(2,2,2)\mapsto \Delta(4,4,2)$…

Looking at the images below, you recognize that the adajency matrix of the graph $A_G$ splits up into three different color submatrices, with $A_G=A_d+A_b+A_d$ (where $d$ is dark, damn...). It's ...
5
votes
0answers
71 views

Bound on number of embassies given that no three countries have pairwise relations

There are 20 countries on the planet,among any three of these countries there are always two with no diplomatic relations. Prove that there are at most 200 embassies on the planet. I tried using ...
5
votes
0answers
114 views

Theoretical link between the graph diffusion/heat kernel and spectral clustering

The graph diffusion kernel of a graph is the exponential of its Laplacian $\exp(-\beta L)$ (or a similar expression depending on how you define the kernel). If you have labels on some vertices, you ...
5
votes
0answers
87 views

Maximum leaf number of an $m \times n$ grid graph?

Are there any results regarding the maximum leaf number of an $m \times n$ two-dimensional grid graph? Either a closed form, or a table of values for small $m$ and $n$?
5
votes
0answers
108 views

Graph Relatives for Tessellation of the Hyperbolic Plane

I'm trying to get into the theory about the Modular group. Among the "Paracompact hyperbolic uniform tilings in [∞,3] family" in the section "Tessellation of the hyperbolic plane" I found the Order-3 ...
5
votes
0answers
42 views

Behavior of the giant component of an Erdos-Renyi graph near p = 1/n

what is the behavior of an Erdos-Renyi random graph with p = (1 + f(n))/n with $f(n)=o(1)$? If $f(n)=0$ then it has size about $n^{2/3}$, but what if the probability is perturbed slightly, say with ...
5
votes
0answers
56 views

Which complete weighted graphs are obtained from finite metric spaces?

Let $(X, d)$ be a finite metric space with $X = \{x_1, \dots, x_n\}$. We can associate to this metric space a complete weighted graph with vertices labelled by the points of $X$, and edges weighted by ...
5
votes
0answers
862 views

Every tree has two leaves. Is my proof ok?

A tree is a connected acyclic graph. A leaf is a vertex of degree one. The distance $d(u,v)$ between two vertices $u$ and $v$ of a graph is the length of the shortest path from $u$ to $v$. Theorem. ...
5
votes
0answers
34 views

Is this the smallest graph with the desired properties?

The above graph has the following properties : $1$) Every vertex is start vertex of some hamiltonian path. $2$) It contains no hamiltonian cycle. $3$) It has no cycle of length $3$. $4$) It is ...