Tagged Questions

Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, ...

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$ ...
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? ...
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 ...
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 ...
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 ...
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 ...
69 views

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 ...
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 ...
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 ...
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 ...
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 ...
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}$$ ...