## New answers tagged graph-theory

1

Let $G=K_\omega$ be a clique on infinitely many vertices and $H$ a disjoint union of $K_n$ for each $n\in\omega$. I claim $\text{Flt}(G,H)$ has no minimal elements.
Let $f:V(G)\to V(H)$ be arbitrary. Take some vertices $v,w\in V(G)$ with $f(v)\in K_n$ and $f(w)\in K_m$ with $n\neq m$. Consider a map $g:V(H)\to V(H)$ which does the following: if $k\neq n,m$ ...

4

This is the problem of finding not-necessary-linear codes in a Hamming cube: for odd dimensions, one could take this table as a lower bound.
EDIT: The Hoffman bound gives a better bound that Fedor Petrov's for even $n$:
The Hoffman bound for a regular graph is $\alpha \leq |V|* \frac{-\lambda}{d-\lambda}$, where $\lambda$ is the smallest eigenvalue of the ...

3

The upper bound is $2^n/(n+1)$ coming from the observation that 1-neighborhoods of red vertices must be disjoint. Sometimes it is tight, say, Hamming codes give an example of exactly $2^n/(n+1)$ red vertices for $n=2^k$. To do it, identify $n$ coordinates with the set $A$ of all vertices of $k$-dimensional cube $\{0,1\}^n$ except the origin $(0,0,\dots,0)$, ...

1

Consider the graph $G$ with vertices $ \left\{ (x,A) |x ∈\mathbb{N} \right\} \cup \left\{ (x,B) |x ∈\mathbb{N} \right\} \cup \left\{ (x,y) |x ∈\mathbb{N}, y ∈\mathbb{N},y \leq x \right\}$ with two vertices $(w,x)$ and $(y,z)$ connected iff $w=y$ or both $x$ and $z$ are letters.
For each $n\geq 2$, one can decide whether to remove the edge $(n,n-1)$ or not;...

4

Adding to the allure of this deadly siren song is the fact that there are constructions of this sort for the Moore graph of degree 3 (the Petersen Graph with 10 vertices and independence number $4$) and the Moore Graph of degree $7$ ( the Hoffman-Singleton graph with $50$ points and independence number $15$.)
WARNING: BEWARE!
PG(3,1) would be a ...

0

Fwiw, a plot of the spectrum of the sum of 10 random permutation matrices
shows the (semi)circle law:

11

How about the star $S_6$? To realize this graph in the way you describe, you would have to map the center point to some $c \in \mathbb R^2$; then you would need to map the $6$ other points of $S_6$ inside the unit circle around $c$, but all at distance $\geq\!1$ from each other. This is impossible.

4

Yes,$\DeclareMathOperator{In}{In}$ this seems to be true. Let $\deg^-(v)$ denote in-degree of $v$ and let $V$ denote the vertex set. We can partition $V$ as $V_f\cup V_<\cup V_{\geq}$ where:
$V_f$ is the set of vertices $v$ with finite in-degree
$V_<$ is the set of vertices $v$ with infinite in-degree and $|\{u\in \In(v)\mid \deg^-(u)<\deg^-(v)\}|=\...

4

The answer is yes for countable graphs:
Fix an infinite graph $G$ and a bijective homomorphism $f:G \to G$. Define $c:[G]^2 \to 2$ as $c(\alpha,\beta)=1$ if $\{f\alpha, f\beta\} \in E(G)$ and $c(\alpha,\beta)=0$ otherwise. Since $G$ is infinite, by Ramsey´s Theorem there is an infinite $c$-homogeneous $H \subseteq G$. If $c \upharpoonright [H]^2$ is ...

4

Think of the hypergraph as a simplicial complex $\Delta$, with the facets being the hyperedges. Consider property (*) as:
1) The $i$-skeleton of $\Delta$ is full for $0\leq i\leq k-2$ and
2) $\tilde H_i(\Delta)=0$ for $0\leq i\leq k-2$
Then these conditions force $f_{k-1}-\binom{n-1}{k-1}= \dim \tilde H_{k-1}(\Delta)$.
Thus a minimal complex ...

0

Consider the dual of the square lattice, which is formed from the square lattice by placing one vertex in the center of each square and joining vertices with an edge when their corresponding squares in the square lattice share an edge.$^{[1]}$
It's easy to see that the edges in the original graph are perpendicular with those in the dual graph. That is to ...

15

Yes, every connected cubic graph is 3-almost-Hamiltonian.
Replace each edge by two parallel edges then follow an Eulerian circuit.
In the case of a bridgeless cubic graph, you can add a perfect matching instead of doubling each edge, which shows they are 2-almost-Hamiltonian.

1

### The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles

$O(k \log k)$ edges would suffice. So $c(n,k)$ is $O(k \log k)$.
We this by showing the following:
Thm 1: let $G$ be a graph on $n$ vertices with $n+K$ edges. There are $\theta(K/\log K)$ edge-disjoint cycles in $G$.
For the proof of Thm 1, we first define for every graph $G'$, the multigraph $f(G')$ formed from $G'$ by (a) taking the 2-core of $G$ ...

1

Well, if you collapse all vertices of distance 2 in a connected graph, then the resulting graph will either be a single vertex (if the graph is not bipartite) or an edge.
But there are graphs where you can identify some of the vertices of distance 2 from each other to increase $\eta(G)$.
Indeed,
First let $G$ be a $K+1$-clique where $K$ is of the form e....

1

The distribution of component size in Erdos-Renyi networks is discussed in many places, and known analytically. A recent reference that summarizes this is in Appendix A of
Eytan Katzav, Ofer Biham, and Alexander K. Hartmann,
Distribution of shortest path lengths in subcritical Erdős-Rényi networks, Phys. Rev. E 98, 012301 (2018).
I hope this helps

1

OP: "Is there any literature on this class of graphs?"
The term "almost-planar graph" is already firmly in the literature:
Guoli Ding, Joshua Fallon, Emily Marshall.
"On almost-planar graphs."
arXiv abstract. Mar. 2016.
"A nonplanar graph $G$ is called almost-planar if for every edge $e$ of $G$, at least one of $G \setminus e$ and $G\,/\,e$ is ...

1

According to Kuratowski's theorem a planar graph is characterized by the absence of (subdivisions of) $K_5$ and $K_{3,3}$, where $K_5$ is the infamous pentagram and $K_{3,3}$ can be visualized as a hexagon with opposite vertices connected by edges and also resembles the smallest Möbius Ladder Graph.
My suggestion to construct extremal graph "almost planar"...

6

No.
Let $P$ be any graph with $\chi(P) = n > 2$. Let $B = K_n$ and let $A$ be $K_{n,n}$ minus a perfect matching $M = \{(c_i,d_i): i \in [n]\}$. A surjective homomorphism $s : A \to B$ is given by mapping both $c_i$ and $d_i$ to vertex $i$ of $B$. Since $\chi(P) = n$, there is some homomorphism $h : P \to B$. But of course there is no homomorphism from $...

3

I think that the Tutte polynomial, as suggested by Fedor Petrov in the comments, is likely what you are looking for. For a graph $G$, this is the polynomial $$ T(x, y) = \sum_{A \subseteq E(G)} (x-1)^{k(A) - k(E)} (y-1)^{k(A) + |A| - |V(G)|}$$
where $k(A)$ is the number of connected components of $(V(G), A)$. Indeed, the Tutte polynomial is well defined for ...

8

There are many categories of graphs, so perhaps it's best to take a synoptic view.
The table below surveys several categories of directed graphs (DG), directed multigraphs (DM), undirected graphs (UG), and undirected multigraphs (UM). The asterisks indicate the ones which are not cartesian closed, in each case lacking a terminal object.
\begin{array}{...

8

Yes, the hexagon ABCDEF with the additional edge of AC has this property. The first graph shows $G$ and the others show two views of $D_2(G)$.
(Graphs courtesy of NCTM)

5

Yes, there is an operad structure. The answer essentially lies in Willwacher's paper Models for the $n$-Swiss-Cheese operad. It's actually a colored operad. The graphs you describe are bicolored: you have the aerial vertices and the terrestrial vertices. Inside a terrestrial vertex, you can insert a graph of the same kind (bicolored). Inside an aerial vertex,...

2

It's probably not the first, but the 1956 paper of Ford and Fulkerson, "Maximal Flow through a Network" used "arcs".

5

A counterexample is the subgraph of the $\mathbb{Z}^2$ Cayley graph found by taking squares $S_i$ of side $i$ and arranging them along a (near)diagonal in a chain so that each $S_i$ is adjacent to $S_{i+1}$ along a single edge, and no other edges connect any $S_i$ to any other.
Suppose the given inequality held. For a given $n$, choose $i > 10n$ and let ...

0

No, any even cycle graph with order not divisible by $3$ is a regular bipartite graph with total chromatic number $4=\Delta+2\,\,,\Delta=2$. Therefore, it may be conjectured that a regular bipartite graph with every cycle(or posibly girth) divisible by $3$ would satisfy being type $1$.

6

Let me start my answer by noting that this is fundamentally the wrong approach to the problem of reducing a large set of graphs by isomorphism type. The best software (nauty, Bliss, Traces) can put a graph into canonical form in an amount of time similar to what testing two graphs for isomorphism takes. After canonical labelling, you can use a sorting ...

3

Why I do not have a relevant counterexample yet, I decided to write an extended comment on related Poincaré and Sobolev inequalities. The purpose was to place the question in the right context, provide a source that contains many related references and mention a result (inequality (*)) in the positive direction that is strictly related to the inequality in ...

0

You can build such a matroid from the circuits of another binary, or representable in general, matroid as well. Some papers make use of such structure, either regarded as a chain group or simply as a subset of a vector space. But to the best of my knowledge I don't think there is a name for such matroids.

1

Meanwhile for fixed e.g, $d=6$ there are infinite families of $d$-regular bipartite graphs that have a total coloring with $d+1$ (here 7) colors.
Let $X=\{x_0,\ldots, x_{n-1} \}$ and let $Y = \{y_0,\ldots, x_{n-1}\}$, where $n$ is a multiple of 42.
Then $x_j$ and $y_{j'}$ are adjacent if $j-j' \in \{-3,-2,-1,1,2,3\}$ arithmetic done mod $n$.
The colors ...

3

No it is not always possible to total color a bipartite graph with $\Delta+1$ colors, even with the given restrictions on $\Delta$ and the number of vertices. This is a counterexample. Let $G$ be a complete bipartite graph with $n$ vertices on each side, where $n$ can be any integer you want as long as it is sufficiently large. [So the degree of each vertex ...

11

It's a bit hard to give a comprehensive answer without knowing exactly what sort of properties you are after, but here is a start. Such graphs are called uniquely colorable graphs (see here and here). For the case of two colors they are characterized as the connected bipartite graphs, but for higher numbers of colors no such characterization is known.
In a ...

6

Definitely not all graphs are minors of $\omega^2$ - $\omega^2$ is obviously a planar graph, and hence so is each of its minors. In fact, it turns out the converse also holds - every planar graph is an induced minor of $\omega^2$. Let me illustrate the construction with a small example. In the following illustrations, each small square is meant to represent ...

8

Check out the Open Problem Garden,
which lists this problem:
Due to MO user @BorisBukh.

0

[community wiki since it's my own question]
The answer is actually simple once the convention on degrees is clear (which it apparently was not at the time of writing)
Answer: If $k$ is odd, a $k$-regular loopless graph is a Schreiers graph if and only if it has a matching.
First note that elements $a \in S$ so that $a \neq a^{-1}$ necessarily create a 2 ...

2

One can also cook up an involution based on unique factorization of connected graphs under various products. A connected graph has a unique representation as a cartesian product of irreductible graphs (connected graphs that cannot be further factored). This was proven by Sabidussi and independently by Vizing. Starting with an arbitrary graph $G$ you can look ...

8

Let $X(\mathcal{S)}$ be the block graph of a Steiner triple system $\mathcal{S}$ on $v$ points. The triple system consists of $b=v(v-1)/6$ triples from a set $V$ of size $v$ such that each pair of points from $V$ lies in exactly one triple. Necessarily $v\equiv1,3$ mod 6 and, if this condition holds, triple systems on $v$ points exist. The block graph has ...

4

As a spin-off of https://mathoverflow.net/a/321171/3032, we have
equidistribution of the two parameters
$
a(G) = \begin{cases}
1 & \text{if $G$ has no vertices of degree $1$}\\
0 & \text{otherwise}
\end{cases}
$
and
$
b(G) = \begin{cases}
1 & \text{if $G$ has no two vertices with the same set of neighbours}\\
0 & \text{otherwise}
\end{...

2

A 3-connected planar graph has a unique embedding in the plane (see https://en.wikipedia.org/wiki/Dual_graph#Uniqueness). And the planar dual of a 3-connected planar graph is again 3-connected. So you define an involution on the set of graphs which acts trivially if the graph is not 3-connected and planar, and replaces 3-connected planar graphs by their ...

0

Well, this is not quite an answer but it may still be helpful and is too long for the comments
The mapping $f: \mathcal{G}_n \mapsto \mathcal{G}_n$ where $f(G)$ is the complement of $G$ on each connected component of $G$, is not a bijection though.
Indeed, let $H_1$ be the graph on $[n]$ and assume $n$ is a multuple of 5, where the connected components of $...

-1

Inspired by the question Regular graph such that $2$ distinct vertices have same neighborhood set, and via https://oeis.org/A004110, I discovered the following article presenting an apparently very non-trivial bijection on graphs:
Kilibarda, Goran, Enumeration of unlabelled mating graphs, Graphs Comb. 23, No. 2, 183-199 (2007). ZBL1116.05038.

5

An infinite family of (strongly?) rigid 3-regular finite graphs can be constructed using the following graph $RC_1$ called the rigid connector:
A graph composed of the chain consisting of $n$ rigid connectors will be denoted by $RC_n$:
Finally, the required rigid 3-regular graph consists of 3 parallel chains $RC_k$, $RC_n$, $RC_m$ for pairwise distinct ...

Top 50 recent answers are included

#### Related Tags

graph-theory × 3432co.combinatorics × 1344

graph-colorings × 291

reference-request × 285

algorithms × 212

pr.probability × 190

spectral-graph-theory × 155

computational-complexity × 145

gr.group-theory × 143

linear-algebra × 119

random-graphs × 118

discrete-geometry × 109

extremal-graph-theory × 104

set-theory × 74

algebraic-graph-theory × 69

mg.metric-geometry × 66

matching-theory × 63

bipartite-graphs × 60

trees × 58

matrices × 57

hypergraph × 51

nt.number-theory × 50

hamiltonian-graphs × 48

infinite-combinatorics × 46

ramsey-theory × 46