# Tagged Questions

**1**

vote

**0**answers

52 views

### Asymptotic results in unbalanced left $d$-regular expander graphs

Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$.
Call a graph $G = (U, ...

**6**

votes

**0**answers

132 views

### The Universal Labeling of graph

The universal labeling of a graph $G$ is a labeling of the edge set in $G$ such that in every orientation $\ell$ of $G$ for every two adjacent vertices $v$ and $u$, the sum of incoming edges of $v$ ...

**8**

votes

**1**answer

167 views

### Spectral lower bounds on the diameter of a graph

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:
$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$
This bound is very elegant but ...

**1**

vote

**1**answer

98 views

### How to model a time-discrete heat equation on a graph?

I would like to know how one can set up a time-discrete model for the heat equation on a graph?
Is this problem using the heat kernel equation on a graph?

**0**

votes

**0**answers

70 views

### Heat equation with graph laplacian

I would like to start with considering the time-dependent heat equation on a connected graph and consider its Laplacian matrix.
Suppose we have a connected graph with unknown temperature on vertices. ...

**0**

votes

**0**answers

71 views

### Eigenvalues of the Cayley-like graph

Let $ F_q $ be a finite field of characteristic 2.
Let $ x^2 + Sx +P \in F_q[x] $ be an irreducible polynomial over $ F_q $,
and let $ g $ be one of its roots in $ F_{q^2} $.
Define a map $ M: ...

**33**

votes

**6**answers

2k views

### Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...

**13**

votes

**1**answer

599 views

### Who first dubbed them “expander graphs”?

Expander graphs
("sparse graphs that have strong connectivity properties")
burst onto the mathematical scene around the millennium, but I have not
been successful in tracing the origin of
(a) the ...

**7**

votes

**2**answers

131 views

### Bounds on chromatic number of $k$-planar graphs

A $1$-planar graph can be drawn in the
plane so that each arc is crossed at most once by another arc.
A $k$-planar graph can be drawn so that each arc is crossed at most $k$ times.
Planar graphs are ...

**19**

votes

**0**answers

665 views

### Non-linear expanders?

Recall that a family of graphs (indexed by an infinite set, such as the primes, say) is called an expander family if there is a $\delta>0$ such that, on every graph in the family, the discrete ...

**5**

votes

**1**answer

155 views

### Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.
The famous Nash-Williams conjecture claims ...

**4**

votes

**2**answers

231 views

### Equality-preserving embeddings of finite trees

For finite trees $T_{1}$ and $T_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be ...

**0**

votes

**1**answer

55 views

### mean length of the non-crossing graphs on n points

My original question is rather vague so I'll start with a precise example and then indicate possible generalisations.
Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...

**8**

votes

**5**answers

994 views

### Are all almost regular graphs obvious?

Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively.
A graph is almost regular if $\Delta-\delta=1$.
Now, here is a simple way to generate ...

**0**

votes

**0**answers

26 views

### number of bipolar orientations to acyclic ones

Given a $k$-regular graph $G$, is there an upper bound on the number of bipolar orientations that $G$ has?
I am trying to show that the number of bipolar orientations is much much lower than the ...

**5**

votes

**0**answers

95 views

### Monotone embedding of complete binary tree in hypercube

Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...

**5**

votes

**0**answers

148 views

### Are the roots of chromatic polynomials plus a fixed constant dense in $\mathbb{C}$?

Alan Sokal proved that chromatic roots are dense in the whole complex plane. I.e., if $P(G;z)$ denotes the chromatic polynomial of a finite simple graph $G$ evaluated at $z \in \mathbb{C}$, then ...

**2**

votes

**3**answers

157 views

### Examples of graph properties characterized by forbidden (not necessarily induced) subgraphs

A graph property is hereditary if it is closed under taking induced subgraphs (equivalently, if it is closed under removing vertices). A graph property is monotone if it is closed under taking ...

**0**

votes

**0**answers

36 views

### Cycle cover of a cubic polyhedral graph

Tutte graph is a counterexample for the Tait's conjecture stating that all cubic graphs are Hamiltonian. For the non-hamiltonian graphs - is it true that all vertices of any such graph can be covered ...

**2**

votes

**0**answers

47 views

### Regular graphs with unimodal subdegrees that are not distance-regular

Distance regular graphs are known to exhibit the following property: starting from an arbitrary vertex $\alpha$, let $k_i$ denote the number of vertices at distance $i$ from $\alpha$ (in terms of ...

**1**

vote

**0**answers

66 views

### labeling vertices in a graph to minimize distance between adjacent vertices

We have a regular graph $G$ of degree $m$ on $n$ vertices and we label each of its vertices with the number $1$ through $n$. What can we say about the maximum difference between the numbers of two ...

**7**

votes

**2**answers

269 views

### Wait time to grid network disconnection with failing edges

Let $G_n$ be an $n \times n$ planar toroidal grid graph, with each node
connected to its four neighbors, with the top row connected to the bottom,
and the right column connected to the left.
Suppose ...

**2**

votes

**0**answers

60 views

### Characterize the equivalence class of bipartite graphs obtained from each other by elementary row operations on their adjacency matrices

Let $M$ be an $m\times n$ matrix real matrix. Let $G$ be a bipartite graph, with partitions $A$ and $B$, such that $|A|=m$ and $|B|=n$. A node $i\in A$ is linked to a node $j\in B$ if and only if ...

**6**

votes

**1**answer

352 views

### Paths in groups

Given a finite group $G$, write $K(G)$ for the complete digraph on the elements of $G$. Label the edge from $g$ to $h$ by element $g^{-1}h$.
Question: For what groups does there exist a Hamiltonian ...

**1**

vote

**1**answer

124 views

### Sequences that represent different drawing of chords?

In combinatorics there are there are special kind of sequences, in which their terms represent the number of different ways that we can draw chords with some properties.
Actually my question is ...

**0**

votes

**0**answers

91 views

### Has this type of Cayley graphs been studied before?

Let $\mathbb F_q $ be a finite field of characteristic 2.
Let $ x^2 + Sx +P \in \mathbb F_q[x] $ be an irreducible polynomial over $ \mathbb F_q $.
Let $$ T = \{ \left( \begin{matrix}
...

**17**

votes

**0**answers

153 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...

**4**

votes

**3**answers

141 views

### Is there any partition of a regular graph which in any part there exists a vertex with all its neighborhood?

Let we have a regular graph. I want to know if we can partition the vertex set of this graph while in any part there exist a vertex with all its neighborhood?

**10**

votes

**1**answer

263 views

### doubly-stochastic isomorphisms of graphs

A doubly stochastic matrix that commutes with the adjacency matrix of a graph is a doubly-stochastic automorphism of that graph (definition by Tinhofer 1986). Each (classical) automorphism of a graph ...

**2**

votes

**1**answer

78 views

### a necessary condition for a nonempty graph being a line graph

Every gragh below will refer to a finite simple graph.
There is a necessary and sufficient condition for a nonempty gragh being a line gragh:
Krausz's Theorem
A nonempty gragh is a line gragh if ...

**1**

vote

**0**answers

112 views

### Relationship betwen eigenvectors

Suppose that we have two matrices A and B. Matrix B is taken from A with one row and one column deleted. On the other hand A is n*n matrix and B is (n-1)*(n-1) matrix and is created by deleting last ...

**1**

vote

**1**answer

108 views

### Cycles in directed graphs

Let G be a finite directed graph (allowing multiple edges). We define a cycle (as usual) to be a sequence of edges $e_0, e_1, \dots, e_{n-1}$ (up to cyclic permutation) such that the terminal vertex ...

**10**

votes

**1**answer

493 views

### Where can I find Gonthier's Coq code proving the four color theorem?

In a 2008 article in the Notices, Georges Gonthier announced a computer-checked proof of the four color theorem using Coq:
Gonthier, Georges. Formal proof—the four-color theorem.
Notices Amer. ...

**6**

votes

**2**answers

106 views

### How to efficiently find a Hamiltonian cycle in a graph whose closure is complete?

A graph whose closure is the complete graph is Hamiltonian by the Bondy-Chvátal theorem, but I haven't found a polynomial algorithm for finding a Hamiltonian cycle in such a graph. Is there one that ...

**1**

vote

**0**answers

122 views

### Basis of periodic tiling of Wang tile

Given a set of Wang tile,
Given 3 periodic tiling: A, B, C
We define 3 vector F[A], F[B], F[C]
each vector correspond to the appearing frequency of each type of tiles in the tiling.
Now, we ...

**2**

votes

**1**answer

90 views

### simple cycle analog in 2D (with application in tiling)

We know that any closed cycle of a graph could be decomposed into sum of simple cycles. To translate this theorem into tiling of 1D (Wang tile). We know that any 1D periodic tiling could be ...

**3**

votes

**1**answer

115 views

### Cayley graph which is isomorphic to the line graph of a complete graph

From the literature, we know that the line graph of a complete graph $L(K_{q})$ is a Cayley graph if and only if $q \equiv 3$( mod 4) is a prime power. Now, if $q \equiv 3$( mod 4) is a prime power, ...

**-4**

votes

**2**answers

81 views

### About planar graphs? [closed]

Can any non-planar graph with n minimum crossing points be 'drawn' on a sphere so the vertice and edge sets are the same and it has a connected subset A with minimum r crossing points and a disjoint ...

**2**

votes

**0**answers

103 views

### Graph theoretical representation of Wang Tile

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution.
However, is there a well established counter-part ...

**1**

vote

**0**answers

84 views

### What is the projective dual of a planar graph?

Everybody learns the usual definition of the dual of a planar graph when edges are preserved and faces are mapped to vertices. Everybody learns the projective duality. What if we apply it to a ...

**3**

votes

**0**answers

55 views

### Maximal $k$-chordal subgraph

Recall that a graph is called $k$-chordal if any cycle $C$ of length $> k$ contains a chord, i.e. an edge joining to non-consecutive vertices in $C$. Let $f(n, k)$ be the minimal number of edges ...

**1**

vote

**1**answer

88 views

### How to calculate the maximum number of rainbows for arbitrary graphs?

This question is inspired by problem 1 of the combinatorics test of the 2012 third round iranian olympiad which is as follows:
We've colored edges of $K_n$ with $n-1$ colors. We call a vertex rainbow ...

**3**

votes

**2**answers

168 views

### Distance between two networks

Suppose you have networks A and B, each with a set of nodes and edges. You want to measure how similar the networks are to each-other. None of the nodes or edges are labelled. What are the metric(s) ...

**3**

votes

**0**answers

76 views

### Reconstructing a function from its variants that negate one argument

Call two functions $g(x_1,\ldots,x_n)$ and $h(x_1,\ldots,x_n)$ from complex numbers to complex numbers equivalent if they are the same up to the order of their arguments. Formally: there is a ...

**6**

votes

**1**answer

154 views

### Integral straight-line embeddings of planar graphs

Wikipedia says (in the article on Fáry's theorem),
"Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The ...

**4**

votes

**1**answer

186 views

### Extremal graph theory for directed graphs

In extremal graph theory, there are results such as
$$t(C_4,G)\geq t(K_2,G)^4,$$
where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and ...

**2**

votes

**1**answer

76 views

### Eigenvalues of a graph and its one-edge-delation graph

Let $G$ be any graph with at least one edge and let $e$ be any edge of $G$. Let $G-e$ denote the subgraph of $G$ obtained by deletion of the edge $e$. Assume that $G$ has $n$ vertices.
Suppose ...

**3**

votes

**1**answer

108 views

### A problem related to routing in a graph

I have come across a new problem - I want to know whether this problem is similar to some existing problem or not.
The new problem is this. There is a tourist who has a having the following ...

**0**

votes

**1**answer

165 views

### Spectral Graph Theory [closed]

Let G be an undirected graph, then
Laplacian Matrix(L(G)) = Degree Matrix (D(G)) - Adjacency Matrix (A(G)).
What is the relationship between laplacian and adjacency spectrum of undirected graphs?

**0**

votes

**1**answer

93 views

### Laplacian matrix of a graph with negative weights

I am trying to calculate the Laplacian and Adjacency matrix of a graphs for positive and negative weights. If a graph be simple with only non-negative weight it is easier. But in my graph I have some ...