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

28
votes
0answers
590 views

Is Erdős' lemma on intersection graphs a special case of Yoneda's lemma?

Under which name is the following proposition filed actually: Every poset $P$ embeds fully and faithfully in the powerset of $P$, ordered by subset inclusion. Let me call it Dedekind's lemma. ...
22
votes
0answers
274 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 ...
17
votes
0answers
536 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 ...
12
votes
0answers
416 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 ...
11
votes
0answers
569 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
295 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 ...
11
votes
0answers
833 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. ...
10
votes
0answers
107 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 ...
10
votes
0answers
171 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
203 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 ...
10
votes
0answers
182 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
190 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
104 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 ...
8
votes
0answers
271 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
224 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 ...
7
votes
0answers
120 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
392 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
27 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
76 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
151 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
77 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
92 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
76 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
161 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
132 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
113 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
248 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 ...
6
votes
0answers
167 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
247 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
375 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
149 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
362 views

What is the probability that a random $n\times n$ bipartite graph has an isolated vertex?

By a random $n\times n$ bipartite graph, I mean a random bipartite graph on two vertex classes of size $n$, with the edges added independently, each with probability $p$. I want to find the ...
6
votes
0answers
153 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
214 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
228 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
214 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
161 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
106 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
82 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
104 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
40 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
55 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
597 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
31 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 ...
5
votes
0answers
73 views

How many hamilton paths can a non-hamiltonian graph have?

What is the maximum number of hamilton paths a graph with $n$ vertices can have without having a hamiton cycle ? If my turbo pascal program works well, the first few values for $3,4,...$ vertices ...
5
votes
0answers
112 views

Is there a name for graphs with the following property?

The property of the graph is the following: For any vertex, there is a hamiltonian path starting with this vertex, but the graph is not hamiltonian. The following graph is a small example: ...
5
votes
0answers
160 views

Name for Number of Ancestors/Descendants of Vertex in Directed Acyclic Graph

Let $G = (V, E)$ be a directed acyclic graph. For each vertex $v \in V$, define the ancestors of $v$ to be the set of vertices $u \in V$ such that there exists a directed path from $u$ to $v$. ...
5
votes
0answers
191 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 ...