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

19
votes
0answers
386 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. ...
13
votes
0answers
414 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 ...
10
votes
0answers
323 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 ...
9
votes
0answers
387 views

Expected value of the distance square

Given two points $X,Y$ on two sides of square $[0,1]\times [0,1]$ ($X:(0,1/2),Y:(1,1/2)$ (PS: My original question is $X,Y$ on opposite of a square, but I think that's not the real case) )and $n$ ...
9
votes
0answers
361 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 ...
9
votes
0answers
163 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
92 views

Algorithm to compute fastest method of collecting $k$ re-spawning items which spawn at $n$ specified points

Let $V = v_1, \dots, v_n$ be the locations the items can spawn at, and let $U = u_1, \dots, u_k$ be the current positions of the items. We will assume a new items spawns instantly every time we ...
8
votes
0answers
175 views

Does this graph have a name?

Does graph shown below from the paper Dissection Graphs of Planar Point Sets by P. Erdos, L. Lovasz, A. Simmons, and E.G. Straus have a name? Does it come from a family of related graphs?
8
votes
0answers
581 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. ...
8
votes
0answers
157 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 ...
7
votes
0answers
173 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 ...
7
votes
0answers
100 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
355 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
77 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 ...
6
votes
0answers
127 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
84 views

Quickest way to solve a matrix one step at a time.

I have a $14\times14$ matrix with a possibility of six states in each position The matrix is random each time. An example matrix would be: $$ \begin{pmatrix} ...
6
votes
0answers
81 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
341 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
128 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
215 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 ...
6
votes
0answers
134 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
181 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
213 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 ...
6
votes
0answers
199 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
50 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 ...
5
votes
0answers
89 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 ...
5
votes
0answers
109 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 ...
5
votes
0answers
58 views

What is the maximum number of edges in an $n$-vertex non-Hamiltonian graph of minimum degree at least $2$?

Q: What is the maximum number of edges in an $n$-vertex non-Hamiltonian (simple) graph of minimum degree at least $2$? This question relates to Maximum number of edges in a non-Hamiltonian graph ...
5
votes
0answers
38 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
101 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
49 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
94 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 ...
5
votes
0answers
164 views

Odd Town Problem.

QUESTION: A town with $n$ inhabitants has $m$ clubs such that each club has an odd number of members and any two different clubs have an even number of common members. Show that $m\leq n$. ...
5
votes
0answers
155 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 ...
5
votes
0answers
88 views

Tilings of the Hyperbolic plane

Given a tiling of the hyperbolic plane projected onto a unit disc such as this which can be considered as a graph. I then define some functions: $f(r) =$ number of graph nodes contained within the a ...
5
votes
0answers
156 views

Get the adjacency matrix of the dual of a 3-connected $k$-regular $G$ without pen and paper

As advised on meta, I'll repost this question, which is close to this one, with the additional condition, that $G$ is 3-connected: Given the adjacency matrix $A$ of a $k$-regular planar ...
5
votes
0answers
89 views

Is Paley-13 graph a unit distance graph in 3D space?

The 13-node Paley graph has vertices 1 to 13 that are connected by an edge when their difference is one of the values $(1,3,4,9,10,12)$ Can this graph be put into 3D space so that all edges have ...
5
votes
0answers
67 views

Homomorphism for a fixed graph NP-complete?

Let $G$ be the following Graph: We want to decide whether for an input structure $\mathcal{S}$ there exists a homomorphism $S \to G$. We will call this problem $HOM_G$. The task at hand is to show ...
5
votes
0answers
318 views

Intersecting Odd Cycles, Chromatic Number, and the Subgraph $K_5$

Consider a graph $G$ such that every pair of odd cycles in G intersect. Then $\chi(G) \le 5$. Furthermore, $\chi(G) = 5$ implies $K_5 \subset G $. Here is the proof of the first claim: Let ...
5
votes
0answers
209 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 ...
5
votes
0answers
63 views

Erdos Ko Rado for hypergraphs of bounded degree?

The Erdos-Ko-Rado theorem states that if $H$ is a $k$-uniform hypergraph on $[n]$ which is intersecting, then $|H| \leqslant \binom{n-1}{k-1}$. The easy example which shows this is tight is just take ...
5
votes
0answers
98 views

What is special about simplices, circles, paths and cubes?

There are some ubiquitous families of graphs — the complete graphs (or simplices) $K_n$, the circle graphs $C_n$, the path graphs $P_n$, and the hypercube graphs $Q_n$ — that intuitively ...
5
votes
0answers
513 views

Embedding Mazes - Spanning Trees of a Grid Graph

A perfect maze (a maze with a unique solution) can be seen as a tree, where each node corresponds to a cell in the maze, and where edges corresponds to passages (missing walls) between cells. Two ...
5
votes
0answers
221 views

Can the 57-cell be made in vZome without strut crossings?

Here's the 57-cell in vZome with lots of strut crossings: Is it possible to construct the 57-cell in vZome without any strut crossings? That is, 57 nodes, 171 struts, in the 57-cell / Perkel graph ...
4
votes
0answers
26 views

all possible values of vertices, given the number of faces and all the vertices have the same degree on a connected planar graph?

A connected planar graph has 26 faces and an unknown amount of vertices (denoted as "V"). All the vertices have the same degree. What are all possible values of V? What I have so far: V + F = E + ...
4
votes
0answers
42 views

Probabilistic counting inequality

I am reading a proof involving the existence of a property in a tournament (a directed complete graph). To make the proof work, we need to have $n^ke^{-n/2^k}<1$. Here $n$ is the order of the ...
4
votes
0answers
67 views

Can bipartite graphs have the following properties?

Let G be a bipartite graph with at least $3$ vertices. Can it have the following properties simultaneously ? $1$) Every vertex is start vertex of some hamiltonian path. $2$) It contains no ...
4
votes
0answers
26 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 ...
4
votes
0answers
49 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 ...
4
votes
0answers
50 views

How many distinct chromatic polynomials are there for simple connected graphs?

For a given order $n$, the number of graphs that are determined uniquely by their chromatic polynomial is A137568. This sequence starting with n=1 is: ...