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

20
votes
0answers
398 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
426 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
325 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
403 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
374 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
165 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 ...
9
votes
0answers
593 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
100 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
183 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
160 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
176 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
102 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
365 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
85 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
111 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
128 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
86 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
84 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
342 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
131 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
221 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
135 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
154 views
+350

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
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
219 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
200 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
78 views

suppose $n$ people are in a party and every two of them have exactly one common friends,prove that there is one who is friend to all.

suppose $n$ people are in a party and every two of them have exactly one common friends,prove that there is one who is friend to all. I suppose there is no one who is friend to all,I want to show ...
5
votes
0answers
52 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
95 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
67 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
40 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
57 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
101 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
181 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
159 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
90 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
158 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
90 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
336 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
216 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
64 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
99 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
190 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 ...
5
votes
0answers
527 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
224 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
43 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
69 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
27 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 ...