Skip to main content

All Questions

Filter by
Sorted by
Tagged with
8 votes
4 answers
1k views

Counting with trees

Let $\mathcal{U}_n$ denote the set of unrooted unlabelled trees with $n$ edges. For $T\in\mathcal{U}_n$, let $1^{u_1}2^{u_2}\cdots n^{u_n}$ be its degree distribution, that is, $u_i=\#$ of vertices ...
T. Amdeberhan's user avatar
3 votes
0 answers
61 views

Is this bipartite equivalent of 1-walk-regular graphs known?

A graph $G$ is 1-walk-regular if for each vertex $v$ the number of closed walks of length $\ell$ starting (and ending) at $v$ depends only on $\ell$ but not on $v$. for each edge $vw$ the number of ...
M. Winter's user avatar
  • 13.6k
3 votes
1 answer
140 views

Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs

It is well known that for a bipartite graph $G$ with bi-adjacency matrix $A$, then $\det A \neq 0$ (as a polynomial) iff $G$ has a perfect matching (there is a similar result for general graphs with ...
Agile_Eagle's user avatar
0 votes
0 answers
57 views

Reference for packing property and König property

Can someone please suggest reference material to study about the packing property and König property of ideals and some examples?
Sowbarnika R's user avatar
0 votes
2 answers
96 views

Isometric path cover number of the 2 dimensional grid graph

I am looking for a proof of the fact that at least $2n/3$ isometric paths (i.e. shortest paths between the end points) are required to cover the vertices of the $n\times n$ grid graph (i.e. Cartesian ...
Pritam Majumder's user avatar
5 votes
0 answers
141 views

If chromatic polynomials for two graphs agree, can I always find an edge such that the two deletion-contraction minors have same chromatic polynomial?

Suppose I have non-isomorphic graphs $G$ and $H$ (which have at least one edge), but such that their chromatic polynomials are the same. Can I then always find an edge $e$ in $G$ and $f$ in $H$ such ...
Per Alexandersson's user avatar
4 votes
1 answer
222 views

Double cover the edges of a complete graph by smaller complete graphs

Suppose we have a complete graph $K_n$ on $n$ vertices. Are there any results on the ways to cover $K_n$ with $k$ copies of $K_m$, for $m<n$, such that each edge of $K_n$ is contained in exactly ...
Wallace Rin's user avatar
2 votes
1 answer
152 views

First known proof of the $2 \cdot n-2$ Theorem for the planar generalization of the Nine dots problem

Reading the Wikipedia page about the well-know Nine dots puzzle, I have just seen that the planar generalization of this problem would have been proven in 1956 (see Wikipedia: Nine dots puzzle), while ...
Marco Ripà's user avatar
  • 1,451
1 vote
1 answer
177 views

Spectral characterization of complete or complete bipartite graphs

The Lemma 6 in this paper mention the following spectral characterization of complete or complete bipartite graphs: Let $G$ be a connected graph with $\ge 2$ vertices. Then $\lambda_2=...=\lambda_{n-...
YuiTo Cheng's user avatar
3 votes
1 answer
158 views

Sharp upper bound of the number of edges for graphs of thickness two

A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known ...
Lorenzo Pompili's user avatar
6 votes
0 answers
373 views

Circle numbers on edges of a graph

Let $k$ vertices in a graph be given. Some pairs of vertices are connected by an edge, each edge is labeled either $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. We can circle some of the numbers on the edges. ...
Karo's user avatar
  • 277
2 votes
0 answers
65 views

Structure Theory for Tree Decompositions

I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer. Is is known when $G$ admits the following type of ...
Timothy_G's user avatar
0 votes
2 answers
157 views

Dense vertex-symmetric graphs with high girth

I am looking for existing constructions of vertex-symmetric graphs on $n$ nodes that have a girth at least $g$ and are dense, i.e., have at least $n^{1 + \epsilon}$ edges, where $\epsilon>0$ may ...
GraphStudent's user avatar
0 votes
0 answers
84 views

Bounds for smallest non-trivial designs

Given $s>t\ge 2$, let $N(s,t)$ be the smallest integer $n>s$ such that there exists an “$(n;s;t;1)$-design” (i.e., a collection of $s$-subsets $e_1,\dots,e_m$ of $[n]:=\{1,\dots,n\}$, such that ...
Zach Hunter's user avatar
  • 3,499
2 votes
1 answer
157 views

Bound for a sequence of vertices in a graph

I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be any $k$-regular connected directed graph with $n$ vertices, no parallel edges and no 2-cycles. For a vertex $v\in G$, let $...
Arturo's user avatar
  • 167
0 votes
0 answers
55 views

Comparing spectral radius of two graphs using the entry of Perron vector

Suppose we have a graph $G$. Let $A$ be the adjacency matrix of $G$ and $x$ be the corresponding Perron vector. Let $x = (x_1,x_2,\cdots,x_n)^t$, where $x_i$ corresponds to the vertex $i \in V(G)$. We ...
User8976's user avatar
  • 199
2 votes
1 answer
173 views

Matching polynomial, but $K_2$ is replaced by $K_3$. Have these been studied?

Given a simple graph $G=(V,E)$, we can consider matchings, $M\subseteq E$, where $M$ is a matching iff no vertex is shared between different edges. The number of edges in $M$ is denoted $|M|$. The ...
Per Alexandersson's user avatar
1 vote
0 answers
74 views

Keller's cubing conjecture but with arbitrary cubes of side $1$

These days I have been reading about Keller's cube tyling conjecture, which asks if in any covering of $\mathbb{R}^n$ by translates of $[0,1]^n$ with disjoint interiors there are two cubes sharing one ...
Saúl RM's user avatar
  • 10.6k
4 votes
0 answers
89 views

How to measure the optimality of the induced order by a median order of a tournament on a big subset

Median orders are great tools for dealing with a-priori unknown orientations of edges in tournaments, because they provide us with local properties on oriented edge density. I've been wondering if ...
alosc's user avatar
  • 71
2 votes
0 answers
165 views

Has Mac Lane's article "When can a graph be mapped on a torus?" been published anywhere?

I came across the following abstract of an article: Mac Lane, S., When can a graph be mapped on a torus?, Bull. Amer. Math. Soc. 42(9), 629 (1936). Abstract #341. MR1563375, JFM 62.0694.07. Q. Does ...
The Amplitwist's user avatar
3 votes
0 answers
144 views

Counting homologically non-trivial and trivial cycles in $n \times n$ square lattice torus of a given length $l \geq n$

This should be a fairly standard question but I can't really seem to find a reference. Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...
Sanchayan Dutta's user avatar
15 votes
1 answer
746 views

Page-turning number of a graph

Motivation. As I was travelling in the UK, I used a physical copy of the "A-Z Road Atlas BRITAIN" for getting around. I was impressed that whenever I wanted to go from the map segment shown ...
Dominic van der Zypen's user avatar
10 votes
3 answers
931 views

"Gluing and copy" graphs

Consider the minimal class of (simple, undirected) connected graphs (strictly speaking, isomorphism classes of connected graphs) which contains a single vertex $K_1$, and is closed under following ...
Fedor Petrov's user avatar
1 vote
0 answers
381 views

Counting number of spanning trees of the complete bipartite with given vertex-degrees

For given $n_1,n_2 \in \mathbb{N}$ let $K_{n_1,n_2}$ be the complete bipartite graph. I have seen a few sources proving that the number of spanning trees $t(K_{n_1,n_2})$ is given by $n_1^{n_2-1} n_2^{...
Ben Deitmar's user avatar
  • 1,295
2 votes
1 answer
254 views

Is there a formula for the number of trees with this extra condition?

A tree $G$ on $n$ vertices $V=\{v_1,...,v_n\}$ is a connected undirected graph which is acyclic. For each tree $G$ one can split the set of vertices $V$ into two disjoint subsets $U,W \subset V$ such ...
Ben Deitmar's user avatar
  • 1,295
0 votes
0 answers
120 views

Does an extension of the B.E.S.T. theorem for multiple Eulerian circuits exist?

Given a directed multigraph $G=(V,E)$ (multiple edges and loops are permitted) the number of distinct Eulerian circuits for $G$ can be calculated with the B.E.S.T. theorem. Does a similar theory for ...
Ben Deitmar's user avatar
  • 1,295
7 votes
2 answers
595 views

A 2-page paper on a lower bound of Ramsey number

I'm looking for a 2-page paper on a lower bound of Ramsey number $R(a,b)$ for some constants $a$ and $b$. The paper was published in 80s or 90s. I googled it for a few days, but I cannot find the ...
Junhee Cho's user avatar
2 votes
2 answers
183 views

Name of an inductively defined sequence of graphs

Let $G_k$ be the graph obtained by applying the following procedure k-times: Start with a graph with single vertex $v$ (Call this graph $H$) Add a vertex $u$ such that $u$ is not adjacent to any ...
GA316's user avatar
  • 1,269
15 votes
1 answer
518 views

Reference request: Moore graphs

It is clear that the term Moore graph was coined by Hoffman and Singleton in their paper On Moore graphs with diameters $2$ and $3$, where they write E. F. Moore has posed the problem of describing ...
Vince Vatter's user avatar
  • 2,339
5 votes
0 answers
231 views

Schröder and graphical logic?

I was actually surprised by a comment by John Baez over at the n-Category Cafe about his surprise that Ernst Schröder, a mathematician of whom he had known through Schröder's work on mathematical ...
Tom Copeland's user avatar
  • 10.5k
6 votes
1 answer
746 views

Relationship between spectral gaps of adjacency and Laplacian matrices of graphs

Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$). Let $A$ be ...
Vilas Winstein's user avatar
3 votes
1 answer
325 views

Is anything written about winning the "Dollar Game" in the minimal number of moves?

I run some Master's projects on Chip-Firing games, using the Holly Krieger's Numberphile video on the topic as an initial motivation, and going on to prove the main theorem stated there (that you can ...
Paul Johnson's user avatar
  • 2,372
22 votes
2 answers
900 views

Is every 1-million-connected graph rigid in 3D?

It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$: Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete ...
Joseph O'Rourke's user avatar
1 vote
0 answers
152 views

Is this graph theory paper in German translated into English?

I recently read such a paper and want to understand the proof idea of ​​this article. However since it is in German and I have not studied German before, I'd like to ask whether this paper has an ...
Licheng Zhang's user avatar
34 votes
1 answer
789 views

Which graphs on $n$ vertices have the largest determinant?

This is a question that seems like it should have been studied before, but for some reason I cannot find much at all about it, and so I am asking for any pointers / references etc. The determinant of ...
Gordon Royle's user avatar
  • 12.7k
1 vote
0 answers
35 views

Term or reference for a set of integer edge weights to guarantee distinct weighted degrees

I am looking for a term or reference describing sets $S$ of $\binom{n}{2}$ non-negative integers such that, for every bijection $w: E(K_n)\to S$ and every pair of distinct vertices $u$ and $v$ in $V(...
subset's user avatar
  • 11
7 votes
0 answers
97 views

What is known about chromatic polynomial of hypergraph at $-1$

Let $H$ be a hypergraph and let $P_H$ denote its chromatic polynomial. I am interested in the best results interpreting $P_H(-1)$. I am interested both in the general case (which I think is hard) as ...
John Machacek's user avatar
2 votes
1 answer
127 views

The density of a tripartite 1-planar graph

1-planar graphs are those can be drawn in the plane so that there is at most one crossing per edge. We know that the maximum number of edges of an $n$-vertex 1-planar graph is at most $4n-8$, and the ...
Xin Zhang's user avatar
  • 1,190
3 votes
2 answers
2k views

Proving that every strongly connected tournament T on at least 4 vertices contains distinct vertices u, v such that T-u and T-v are strongly connected

I have a two part question: Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?...
Louis D's user avatar
  • 1,701
8 votes
0 answers
181 views

Self-avoiding walks on strips

A strip is a locally finite graph which admits a quasi-transitive (i.e. finitley many orbits on vertices) action of $\mathbb Z$. A self avoiding walk is a walk which visits no vertex more than once. ...
Florian Lehner's user avatar
2 votes
1 answer
181 views

Generators of sandpile groups of wheel graphs

In the paper "On the Sandpile Group of a Graph" by Cori and Rossin one can find a result related to the structure of the sandpile group of $W_n$. Is there a way to provide a set of ...
castor's user avatar
  • 298
3 votes
2 answers
406 views

What is the definition of brick product of graphs?

Can anyone help me with the exact definition of brick product of graphs, say path, cycle. I am not able to find a paper with a clear definition on the internet. Can anyone give me a URL to such a ...
sriram's user avatar
  • 101
0 votes
0 answers
142 views

Counting special paths on a certain rectangle integer grid (binary matrix)

Crossposting from MSE after getting no answers. The bounty on the MSE question is still open, but not for long. Be advised that the comments of the MSE question regard an obsolete version, and that ...
PalmTopTigerMO's user avatar
2 votes
0 answers
86 views

Optimal paths in set-weighted graphs

Let $G = (V,E)$ be an $n$-vertex graph, let $R$ be a finite set (to be specific, let us assume that $R = [n]$), and let $W : V \rightarrow 2^R$. Let us call the pair $(G, W)$ a set-weighted graph. Now ...
Victor's user avatar
  • 655
7 votes
0 answers
74 views

Graphs all of whose cuts are positive

Let $(V, E, w)$ a weighted graph, with vertices $V$, edges $E$, and signed weight $w:E\to \mathbb R$. I am interested to know other popular properties that are known to imply, or are equivalent to, ...
Mircea's user avatar
  • 2,041
5 votes
2 answers
391 views

Conjecture about minimal number of edge crossings in complete bipartite graphs

I am interested in the status of the conjecture about the minimum number of edge crossings $cr(K_{m,n})$ in a drawing of the complete bipartite graph $K_{m,n}$. The Wikipedia article https://en....
Ruth-NO's user avatar
  • 125
5 votes
1 answer
258 views

A graph similar to the Bruhat graph, what is it called?

The weak Bruhat graph (or 1-skeleton of the permutohedron) $B_n$ can be constructed as follows: the vertices of $B_n$ are the permutations of the tuple $(1,...,n)$, two are joined by an edge, if they ...
M. Winter's user avatar
  • 13.6k
1 vote
0 answers
134 views

Counting unions of unlabelled connected graphs

My question can be stated as follows: let $X$ be a hereditary family of unlabelled graphs closed under disjoint unions. Suppose we know, for each $n$, the number $c_n$ of connected graphs in X on $n$ ...
Bogdan's user avatar
  • 183
1 vote
0 answers
121 views

Cheeger constant of truncated hypercube

Look at the $d$-dimensional hypercube and truncate it. This means one replaces each vertex by a cycle (of length $d$) in such a way the the new graph is 3-regular. Question 1: What is the asymptotic ...
ARG's user avatar
  • 4,432
10 votes
1 answer
492 views

is there a ‘nice’ lattice on the set of unlabelled graphs with $n$ vertices?

It is easy to endow the set of vertex-labelled graphs with $n$ vertices with a lattice structure: take the union and the intersection of the edge set as meet and join respectively. However, I wonder ...
Martin Rubey's user avatar
  • 5,822