**5**

votes

**1**answer

162 views

### The number of connected components of a generalized hypecube

For $n$ and $m$ positive integers $n>m\ge 1$ define a graph as follows.
The vertices are the binary strings of length $n$.
Two vertices are adjacent if they differ in exactly $m$ consecutive bits. ...

**2**

votes

**1**answer

95 views

### A 3-connected graph property by Tutte

Tutte （1961): A graph $G$ is $3$-connected if and only if there exists a sequence
$G_0, ...,G_n$ of graphs that have the following two properties
1) $G_0 = K_4$ and $G_n = G$
2) $G_{i+1}$ has an ...

**3**

votes

**0**answers

37 views

### Balancing out edge multiplicites in a graph

Let $G$ be a multigraph with maximum edge multiplicity $t$ and minimum edge multiplicity $1$ (so that there is at least one 'ordinary' edge).
Is there some simple graph $H$ such that the $t$-fold ...

**7**

votes

**0**answers

108 views

### A published proof for: the number of labeled $i$-edge ($i \geq 1$) forests on $p^k$ vertices is divisible by $p^k$

Let $F(n;i)$ be the number of labeled $i$-edge forests on $n$ vertices (A138464 on the OEIS). The first few values of $F(n;i) \pmod n$ are listed below:
$$\begin{array}{r|rrrrrrrrrrr}
& i=0 ...

**5**

votes

**2**answers

211 views

### Average number of distinguished leaves in a binary tree

By a binary tree, I mean in this question a full rooted binary tree in which left and right child are labeled. A leaf of such a tree is a vertex of degree at most 1 (most references would probably ...

**3**

votes

**1**answer

628 views

### Color identical pairs and the 4-color theorem

If one could prove that for every 4-chromatic planar graph $X$ every color identical pair in $X$ is separated by a cycle, would that be a proof of the 4-color theorem?
Explanation:
A pair of ...

**2**

votes

**0**answers

57 views

### Smallest distribution of points with genuinely different clusterings

An hierarchical clustering algorithm for (finite) sets of points in a given metric space is essentially determined by its linkage criterion, which defines the distance between arbitrary (finite) sets ...

**0**

votes

**0**answers

79 views

### The largest size of a boolean subgraph (a hypercube) of a given graph

Let $G(\mathbb{F}_2^n)$ denote the graph that represents the lattice of all subspaces of $\mathbb{F}_2^n$ (also called a Hasse diagram). I am interested in knowing if there exists a large hypercube ...

**5**

votes

**2**answers

197 views

### Genus of Tutte-Coxeter Graph

What is the genus of the Tutte-Coxeter graph -- the incidence graph of the
GQ of order 2? Seems like it should be well known, since nearly every other
parameter for that graph is known, but I can ...

**4**

votes

**1**answer

98 views

### genus of a finite simple undirected graph

Let $G$ be a finite simple undirected graph. Suppose there exist subgraphs $G_1,G_2,\dots,G_n$ of $G$, such that $G_i$ and $G_j$, have no common edges and have at most two common vertices, for each ...

**3**

votes

**2**answers

149 views

### Is the domination number of a combinatorial design determined by the design parameters?

Let $D$ be a $(v,k,\lambda)$-design. By the domination number of $D$ I mean the domination number $\gamma(L(D))$ of the bipartite incidence graph of $D$.
Is $\gamma(L(D))$ determined only by ...

**5**

votes

**2**answers

91 views

### Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?

A tournament is an orientation of a complete graph. A feedback arc set is a set of arcs in a digraph whose removal leave the digraph acyclic. The feedback arc set problem consists in finding a ...

**15**

votes

**1**answer

563 views

### Paul Erdős: Determine or estimate the number of maximal triangle-free graphs on n vertices

Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
...

**4**

votes

**1**answer

133 views

### Nash Equilibrium in general graphical game

Any one has any ideas about how to compute the Nash Equilibrium in general graphical game? Especially, when the graph structure is not a tree.

**5**

votes

**1**answer

149 views

### The proof of Belyi theorem by Lando and Zvonkin

I'm sorry for asking such a specific question, but i have trouble understanding one detail in the proof of Belyi's theorem in the book "Graphs on surfaces and their applications" by Lando and Zvonkin" ...

**3**

votes

**1**answer

132 views

### Is the domination number NP for non-bipartite graphs?

Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?

**2**

votes

**0**answers

90 views

### Proofs about Forbidden Minors

I am working on a problem which involves proving that a particular graph is a forbidden minor of the class of graphs that i am working on.
Now i read kuratowskis theorem for planarity but i still ...

**2**

votes

**1**answer

171 views

### Coloring vertices in a cubic lattice graph and counting edges between vertices of identical and vertices of distinct coloration

Take an $A \times B \times C$ cubic lattice graph $G$, and paint $k_1$ vertices with color $c_1$ & $k_2$ vertices with color $c_2$, where $(k_1 + k_2)$ is equal to the total vertex count. Let ...

**4**

votes

**1**answer

148 views

### Which hyperbolic tilings are Cayley graphs?

I realise the question is easy but after asking to a few people (and never getting a clear answer), I thought it could be instructive to ask it here:
Given a regular tiling of the hyperbolic plane is ...

**5**

votes

**1**answer

343 views

### Flow of an integer

I've stumbled across this family of flow networks, and posted the sequence of maximal flows to OEIS: A238729. I can't find any reference to it either. Has anyone seen it?
Here is the description:
...

**8**

votes

**0**answers

211 views

### Connections between Riemann hypothesis for curves over finite fields and Ramanujan property for graphs

this question relates to the beautiful construction of expander graphs using Cayley graphs of $PGL_2(\mathbb{F}_q)$, as exposited by Davidoff-Sarnak-Valette in their book, Elementary Number Theory, ...

**13**

votes

**1**answer

633 views

### Is every graph the center of some other graph?

The center of a graph $G$ is the set of vertices that minimize the largest
distance to vertices in $G$, e.g., in the graph below, that radius is $4$:
Define the ...

**12**

votes

**3**answers

279 views

### How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seems to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...

**1**

vote

**1**answer

103 views

### Non-toroidality of a simple graph

Let $G$ be a simple undirected graph and $G_1$ and $G_2$ are two subgraphs of $G$, with $E(G_1) \cap E(G_2) =\emptyset$. Which of the following conditions would imply that $G$ is not toroidal:
a; ...

**3**

votes

**1**answer

109 views

### The spectral radius of a modified graph

Let $H$ be a graph and let $G=H \vee K_{1}$ be obtained by creating a new vertex and joining it to every vertex in $H$.
This situation has many different names: $G$ is called the cone or the ...

**3**

votes

**1**answer

185 views

### Calculating a generalized inverse (Moore–Penrose pseudoinverse)

I am considering a graph with $n$ edges with the following nicely structured adjacency matrix:
\begin{equation}
A_n=
\begin{pmatrix}
0 & 0 & 0 &\cdots & 0 & 0 & 1\\
0 & 0 ...

**3**

votes

**0**answers

70 views

### When is an induced subgraph of a Johnson graph hamilton-connected?

The Johnson graph $J(n,k)$ has vertices which are the $k$-subsets of $\{1, 2, \dots, n\}$ where two vertices are adjacent iff their intersection has size $k-1$. A graph is hamilton-connected if every ...

**4**

votes

**2**answers

614 views

### Do Random Walks on the Hexagonal Lattice have a limit?

For every positive integer $n$, consider a regular hexagon $\mathrm{H}_n$ such that
the distance of each vertex from the center is $\frac{1}{\sqrt{n}}$. That in turn
induces a tiling of ...

**4**

votes

**0**answers

141 views

### Does the concept of connective constant make sense for any tiling of the plane?

First let me define what is the "connective constant" of a two dimensional lattice.
Let $c_{n}$ denote the number of $n$ step self-avoiding walks starting from a fixed origin point in the lattice. ...

**1**

vote

**4**answers

269 views

### Graphs with dangling edges

In conventional Graph Theory the role of Nodes and Edges is skewed: nodes are perfectly ok being aloof, but poor edges are always drawn between existing nodes (that is, the two maps from EDGES to ...

**2**

votes

**2**answers

126 views

### Normal subgroups of automorphism group of infinite cubic tree

Let $T$ denote the unique (countably infinite) tree in which every vertex has degree $3$ and let $G=Aut(T)$ be the group of graph automorphisms of $T$.
I'm interested in the properties of this ...

**6**

votes

**1**answer

160 views

### What is/are the best bound/s on the sum of squares of degrees in a graph?

Let $G$ be a graph with degrees $d_{1},\ldots,d_{n}$. I am interested in upper bounds on
$$
\sum_{i=1}^{n}{d_{i}^{2}}.
$$
An example is de Caen's bound:
$$
\sum_{i=1}^{n}{d_{i}^{2}} \leq ...

**-2**

votes

**1**answer

182 views

### Natural constructions (not depending on parameters) [closed]

Consider graph clusterings as a prototypical example of (logical) constructions.
Let a clustering of a graph $(V,E)$ be any covering of $V$, i.e. a set $C$ with $\bigcup C = V$.
I am looking for a ...

**7**

votes

**1**answer

403 views

### Seeming contradiction about P vs NP between graphclasses.org and at least two papers about clique in even-hole-free graphs

I believe correctness about clique in even-hole-free graphs
of graphclasses.org
and the paper Vertex elimination orderings for hereditary graph classes, Pierre Aboulker, Pierre Charbit, Nicolas ...

**4**

votes

**0**answers

138 views

### Genus of the graph $K_{m,2,2,2}$

What is the genus of this complete $4-$partite graph, $K_{m,2,2,2}$, where $m \in \mathbb{N}$?
Thanks in advance.

**0**

votes

**1**answer

119 views

### Which graph topology has the greatest eigenvalue?

I am looking at comparing multiple graph topologies based on their spectra. From the set of all $N\times N$ adjacency matrices, is there any result which points to the adjacency matrix with the ...

**3**

votes

**1**answer

593 views

### Big binary tree as an induced subgraph

I believe this is true:
Suppose $G$ is a graph. If $G$ has a subdivision of a large binary tree, prove that $G$ has an
induced subgraph which is a subdivision of a large binary tree or the line ...

**10**

votes

**2**answers

178 views

### Big Mono-Chromatic Subgraphs of Vertex 2-Colourings

I'm not a graph theorist, but the following quantity came up in my work and I'm curious if it has been studied. Given a connected finite graph $\Gamma = (V,E)$ define: $$ c(\Gamma) = \min_{f : V ...

**1**

vote

**1**answer

94 views

### almost equitable partitions and spectra

If a graph $G$ has an equitable partition, then its charachteristic polynomial (for the adjacency matrix) has a divisor that can be seen as the characteristic polynomial (for the adjacency matrix) of ...

**1**

vote

**1**answer

110 views

### How many edges can you put in a graph such that every edge belongs to a minimal $k$-cycle?

I am trying to solve:
Given $n, k$, find maximum $m$ such that there exists a graph on $n$ nodes, $m$ edges such that every edge is part of a minimal $k$-cycle.
I only care about the asymptotic ...

**2**

votes

**1**answer

130 views

### Non-exchangeable unimodular graph

Let $G=(V,E)$ be an countably infinite, locally finite transitive graph. Say that $G$ is exchangeable if for every two vertices $v,w \in V$ there exists a graph homomorphism that maps $v$ to $w$ and ...

**3**

votes

**1**answer

124 views

### Genus of a simple graph

Let $G$ is a finite simple undirected graph. Suppose there exist subgraph $G_1,G_2,\dots,G_n$ of $G$, such that $G_i \cong K_5$ or $K_{3,3}$, $E(G_i)\cap E(G_j) = \emptyset$ and $|V(G_i)\cap V(G_j)| ...

**5**

votes

**3**answers

260 views

### How hard is it to determine if a weighted graph can be isometrically embedded in R^3?

Consider a graph $G$ with nonnegative edge weights.
Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight?
...

**0**

votes

**0**answers

52 views

### A particular method of removing edges from strong di-graphs

I have been mulling over a little puzzle I gave myself involving a particular type of iterative removal of edges from a digraph and I'm stuck -- thought I'd consult experts.
Start with an ...

**1**

vote

**0**answers

30 views

### Harmonic Bergman spaces on graphs

Harmonic Bergman spaces on Euclidean domains are a set of harmonic functions on a domain that are from $L^{p}$ of that domain. I tried to find something on harmonic Bergman spaces on graphs because we ...

**3**

votes

**0**answers

161 views

### vertex transitive and Cayley graphs

(all the graphs alluded to below are finite).
Suppose I gave you a graph, and asked you whether it was vertex-transitive. How hard is that algorithmically?
The second question is: suppose I gave you ...

**4**

votes

**1**answer

179 views

### Reference request: “unoriented composition” in generalized categories

I'm looking for a generalized notion of category (really of symmetric multicategory) which, roughly speaking, doesn't make a distinction between sources and targets. Each "morphism" in such a category ...

**8**

votes

**1**answer

320 views

### A combinatorial problem concerned with logic circuits

Consider a logic circuit with two-bit gates only. The length of each gate is the number of bit lines that the gate crosses. How hard is to compute the maximum length for a given circuit? Notice that ...

**4**

votes

**1**answer

364 views

### Genus of a graph

Let $G$ is a simple undirected graph. Suppose $G$ has two subgraphs $G_1$ and $G_2$, such that $E(G_1)\cap E(G_2) =\emptyset$ ($E(G_i)$, stand for the set of edges of $G_i$). Then is it true that ...

**3**

votes

**2**answers

334 views

### A structure of the group of automorphisms of an infinite binary tree

My friend asked me to ask his question here. Where he can find (a paper or a book) containing a complete description (with the proof) of a structure of the group of automorphisms of an infinite binary ...