**3**

votes

**0**answers

87 views

### The degree/diameter problem for even girth graphs starting with upper bound

I posted this on stackexchange but due to a lack of response there I am posting here.
Let $G$ be a graph with girth $g$, minimal degree $\delta$, maximal degree $\Delta$, and diameter $D$. Define ...

**3**

votes

**1**answer

110 views

### Construction of planar embedding

I'm reading the following paper on universality considerations in VLSI circuits
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In Theorem 2 On the second page it states there exists ...

**7**

votes

**3**answers

225 views

### Embedding planar graphs into the grid

I've seen the following lemma in a paper. The result is by Valiant.
A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**6**

votes

**1**answer

147 views

### Refinement of Dirac's theorem on Hamiltonian graphs

Dirac's theorem states that if degree of each vertex of a graph $G=(V,E)$ is not less than $|V|/2$, then it has Hamiltonian cycle. It is less known, but still known and not so hard to prove (though I ...

**5**

votes

**2**answers

223 views

### SVD vs Fourier analysis for data.

Fourier analysis is useful for analysis in the frequency domain. SVD on the other hand is useful for analysis of data, and expressing noise in the data. I have a problem that needs extensive data ...

**0**

votes

**1**answer

63 views

### Different graphs with the same open neighborhood hypergraph

For any set $X$ we let $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$.
Let $G=(V,E)$ be a simple, undirected graph. Its open neighborhood hypergraph $\mathcal{H}(G)$ has the same vertex set $V$ with a ...

**2**

votes

**1**answer

86 views

### First passage percolation for general graphs

There have been many questions about the behavior of first-passage percolation on specific graphs. In particular, it seems like cliques, grids, random graphs, and ladders are well-studied. But I can't ...

**1**

vote

**1**answer

59 views

### The existence of a specific partition of the edge set of $K_{2n}$

Let $n$ be an even positive integer and $K_{2n}$ be the complete graph on $2n$ vertices. There are $\dfrac{1}{2}{{2n}\choose n}={{2n-1}\choose n}$ subgraphs of $K_{2n}$ which is isomorphic to ...

**2**

votes

**0**answers

277 views

### Maps between graphs defined through laplacian operations

Edit: The views/answers ratio on this question tells me that it was too long. As such, I've stripped out examples and now ask the question in brief. For examples, please ask in the comments or look at ...

**6**

votes

**1**answer

88 views

### Above/below directed graph on cells of arrangement of lines

This question concerns the structure of a directed graph
built on the cells of an arrangement of lines.
My basic question is whether this graph has been
studied before, perhaps in another guise. I ...

**1**

vote

**2**answers

99 views

### Application of cospectral graphs

Cospectral graphs are graphs having same eigenvalues. Constructions of cospectral graph is an interesting question in graph theory. Now a days we use graph theory in different brunches of Sciences and ...

**1**

vote

**0**answers

76 views

### Computing the Edge Chromatic Polynomial of a graph

Is there a recursive formulae to compute the edge chromatic polynomial of a graph?
The following formulae is known for the vertex chromatic polynomial of a grapg $G$
$P(G,x)=P(G-uv, x)- P(G/uv,x)$ ...

**4**

votes

**1**answer

206 views

### Counting trees according to endpoints

Question: Is there a nice (or any) formula for the generating function
$$T(x,y) = \sum_{m,n} t_{m,n} x^my^n,$$
where $t_{m,n}$ is the number of trees with $m$ vertices and $n$ endpoints?
...

**3**

votes

**1**answer

156 views

### Number of nodes in a given distance in (random) regular graph

Given a d-regular graph $G=<V,E>$ (connected, unweighted & simple), and a node $v$.
denote all nodes with distance $k$ from $v$ $$L_k=\{u\in V : dis(v,u) = k\}$$
Let's call it "the k-th ...

**6**

votes

**2**answers

114 views

### Class of hypergraphs that are always the neighborhood hypergraph of some simple graph

Let $G=(V,E)$ be a graph. Its (open) neighborhood hypergraph $\mathcal{H}(G)$ has the same vertex set $V$ with a hyperedge for the (open) neighborhood of every vertex $v \in V$.
It seems that not ...

**3**

votes

**0**answers

35 views

### Is every 1-skeleton of a 4-tope Steinitzian?

Call a graph "polyhedral" if it is simple, planar, and 3-connected. For example, the 1-dimensional skeleton of every 3-dimensional convex polytope, regarded as a graph, is polyhedral. By a theoreom ...

**3**

votes

**1**answer

117 views

### Complexity of a very simple graph partitioning problem

The following problem seems like a very simple and natural one, but I am not familiar with any existing work on it; in particular I am hoping to prove it is NP hard:
Let $G$ be a complete weighted ...

**1**

vote

**0**answers

69 views

### Lp norm estimates for the inverse of the Laplacian on a graph

I am looking at a finite connected graph and I would like to know what is the best [i.e. largest] constant $\lambda_p$ in
$$
\sum_x f(x) =0 \implies \| \Delta^{-1} f\|_{\ell^p} \leq \lambda_p^{-1} ...

**1**

vote

**1**answer

74 views

### Similarity graph for continuous maps between Hausdorff spaces

Let $X, Y$ be topological spaces and $f,g: X\to Y$ continuous. Then we say that $f, g$ are similar if for all $V\subseteq Y$ open we have either
$f^{-1}(V) = g^{-1}(V) = \emptyset$, or
$f^{-1}(V) ...

**1**

vote

**1**answer

87 views

### Probability of having no cycles of fixed length in $d$-regular graphs

According to this paper, the probability that a random $d$-regular graph of order $n$ has no cycles of length $c_1,c_2,\ldots,c_t$ is $$P=\exp\left(-\sum_{i=1}^t\mu_i+o(1)\right)$$ as ...

**3**

votes

**3**answers

103 views

### Algorithm to determine isomorphism of 2 maximal planar graphs

I read on wikipedia that there are efficient algorithms to answer the question whether 2 (maximal) planar graphs F and G are isomorphic. However, after some (IMHO) substantial searching I don't seem ...

**4**

votes

**1**answer

144 views

### Partitioning ${\cal P}([[1,n]])$

In an analysis of the Jacobi method for the computation of the spectrum of a Hermitian matrix, I face the following problem.
Denote ${\cal P}_2(n)$ the set of doubletons $\{a,b\}$ in ...

**3**

votes

**1**answer

96 views

### Method to construct a bipartite graph G' with 2n vertices from a graph G

I have seen mentioned in a talk an operation that takes a graph $G=(V,E)$ and constructs a new bipartite graph $G'=(V',E')$ such that $V' = V\times \{0,1\}$ and $E'=\{((i,1),(j,0)) : (i,j)\in E\} \cup ...

**6**

votes

**3**answers

237 views

### Generating (or availability of) large strongly regular graphs

Are there collections of already generated large strongly regular graphs available to download? By large I mean $n \geq 200$ where $n$ is the number of vertices. I found Ted Spence's page on srgs, ...

**1**

vote

**1**answer

71 views

### approximate diameter of polytopes in high dimensions

I just came across the following problem:
Let us consider the unit corner of the n-cube
$$
\Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 ...

**1**

vote

**1**answer

97 views

### Are constructive characterisations of k-regular (simple) graphs known?

By a constructive characterisation I mean a theorem giving a list of base graphs and a list of operations such that every graph in a given class is generated from the base graphs by applying some ...

**11**

votes

**2**answers

208 views

### What are some useful invariants for distinguishing between random graph models?

Quite a few probabilistic algorithms for generating random graphs exist in the literature, such as:
The Erdős-Rényi model
The Stochastic Block model
The Watts-Strogatz model
The Barabasi-Albert ...

**2**

votes

**0**answers

64 views

### Non-existence of commutative rings with many nilpotent elements with some restrictions where matrix powers are efficient

At the moment can't find better reference than "Cycle Enumeration using Nilpotent Adjacency Matrices with Algorithm Runtime Comparisons"
though certainly there are others.
Consider the following ...

**2**

votes

**1**answer

67 views

### Maximum and minimum diameter of categorical graph product

Let $G_i$ be connected finite simple undirected graphs with diameter $d_i$ for $i=1,2$. Assume that $G_1\times G_2$ is connected. (Here $G_1\times G_2$ denotes the categorical product.)
In terms of ...

**1**

vote

**0**answers

87 views

### What characteristic of a graph depend on the vertex labeling?

Different labeling on a graph produces class of isomorphic graphs. Two isomorphic graphs possess similar characteristic such as connectivity, degree distribution of vertices, equality of spectrum and ...

**5**

votes

**0**answers

97 views

### “Edge Density” of Infinite Planar Graphs

Given an infinite planar graph $G$, let's denote by $\{H_1,H_2,\dots,H_m\}$ all the labeled graphs on $n$ vertices that appear as subgraphs of $G$. Also let
$$d_n=\frac{\sum_{i=1}^m \#E(H_i)}{nm}$$
...

**1**

vote

**0**answers

193 views

### “Graph Individualization”[ reference request] [closed]

Context: I am studying Weisfeiler Lehman method(WL method) and have clear idea about 1 and 2 dimensional WL method. I was wondering about the individualization process described below-
...

**3**

votes

**1**answer

322 views

### inequality with exponents

We are given a graph $G$, each vertex $v$ has an assigned value $\gamma_v\in [0,1]$, and it happens that for every $v$ we have $\gamma_v+\sum_{u\in \delta(v)} \gamma_u = 1$. Assume that $\sum_v ...

**2**

votes

**1**answer

153 views

### Embedding graphs into hyperbolic spaces

Do we know of a characterization as to when does a graph have a "good" embedding into a hyperbolic space? (And does having such an embedding have a spectral or wavelet analysis signature?)
I don't ...

**4**

votes

**1**answer

259 views

### Can every permutation group be realized as the automorphism group of a graph (acting on a subset of the vertices)?

By Frucht's theorem, every finite group can be realized as the automorphism group of a finite undirected graph. Because a permutation group is a finite group, it is clear that every permutation group ...

**3**

votes

**0**answers

94 views

### Does this notion of “$\mathcal{F}$-digraph” appear in the literature?

By a digraph, I mean a quiver with no multiple edges. So in particular:
Loops are okay.
An infinite set of vertexes is okay.
Furthermore, I will tend to identify each digraph with its underlying ...

**2**

votes

**2**answers

200 views

### Hedetniemi's conjecture for graphs with countable chromatic number

Are there graphs $G, H$ such that $\chi(G) = \chi(H) = \aleph_0$, but $\chi(G\times H) < \aleph_0$?

**16**

votes

**4**answers

713 views

### What algebraic structures are related to the McGee graph?

Recall that an $(n,g)$-graph is a simple graph where each node has $n$ neighbors and the shortest cycle has length $g$, while an $(n,g)$-cage is $(n,g)$-graph with the minimum number of nodes.
The ...

**-1**

votes

**1**answer

97 views

### Categorical product of graphs and chromatic number

Let $(G_i)_{i\in I}$ denote a family of simple, undirected graphs (finite or infinite). Let $\prod_{i\in I}G_i$ denote their categorical product. Why do we have the inequality
$$\chi(\prod_{i\in ...

**1**

vote

**0**answers

136 views

### 3-regular (cubic) graph with adjacency eigenvalue 1

Suppose $A\in\{0,1\}^{n\times n}$ is the adjacency matrix of a 3-regular (cubic) graph $G=(V,E)$; that is, all $n$ vertices $v\in V$ in the graph have three neighbors.
Is there a nice necessary ...

**2**

votes

**2**answers

160 views

### Detecting HNN-Extension and free products with amalgamation

This question is partly connected with the following Connection between Stalling's end theorem and Seifert-van Kampen Theorem.
By Stalling's Theorem a group with more than one end splits over a ...

**3**

votes

**1**answer

111 views

### Good broad review of agent-based modeling? [closed]

Trying to find some good review of agent-based models and networks, specifically models that are defined by a graph of interacting nodes, that covers analysis of collective behavior based on model of ...

**2**

votes

**0**answers

97 views

### Obtaining a quasi-isometry of the 'boundary'

It is well-known that a quasi-isometry induces a homeomorphism on the space of ends of say a locally finite graph for simplicity. Clearly the converse is not true. In other words the concept of ends ...

**1**

vote

**1**answer

206 views

### Can we estimate the probability $\mathbf{P}(a-k|a - b) $ on a random graph?

Let $G=(V,E)$ be an undirected random graph such that
$V$ is the set of nodes, and $E$ is the set of edges
Assume the ground graph $G$ is sparse enough, for example, $\frac{|E|}{|V|}= c \in [10, ...

**0**

votes

**1**answer

119 views

### Reference request: Strong Connectivity and the Incidence Matrix

Question: What would be a good reference for characterizations of strong connectivity of a digraph in terms of its incidence matrix?
Details: Consider a digraph $(V, E)$ with vertex set
$$V = ...

**10**

votes

**2**answers

349 views

### Is every metric space quasi-isometric to a graph?

I've proved that if $(X, d)$ is a geodesic metric space then there exists a graph which is quasi-isometric to $X$...during this proof I've precisely used the fact that given two point in $X$ there ...

**5**

votes

**0**answers

85 views

### Diameter of the modified bubble-sort graph

The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...

**0**

votes

**1**answer

93 views

### Forbidden Tripartite Graphs

I was looking at extremal graph theory. I have understood the proofs of upper bounds for the Zarankiewicz problem which basically states: What can you say about the edges of a graph with $n$ vertices ...

**1**

vote

**0**answers

16 views

### Properties of Optimal k-Tour Spanners

Let the edge set of a Optimal k-Tour Spanner of a graph $G$ be equal to the edges of $G$ that lie on at least one optimal tour through exactly $3<k<n$ distinct vertices of $G$.
I would like ...

**1**

vote

**0**answers

109 views

### Classification of Automorphism set of a Regular graph

Let $A$ be the adjacency matrix of an $r$-regular graph $G$ with $n$ vertices (Not complete or cycle graph) . Also, let $Aut(G)$ be the set of all its automorphisms (i.e. set of permutation ...