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, ...

learn more… | top users | synonyms

6
votes
1answer
125 views

Hamiltonicity criteria for sparse graphs

Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course). There are three main classes of criteria for Hamiltonicity that I am aware of: ...
1
vote
0answers
46 views

Perfect Matchings in Biclique Decompositions of Multigraphs

Suppose you have the $K_{2n}$ covered by a multigraph consisting of $2n-1$ bicliques, each consisting of a partition of the vertex set into two sets of equal size. Here is a picture of $K_{6}$ with 5 ...
3
votes
1answer
50 views

Are all (non-constant) symmetric submodular functions non-monotone?

I am trying to show (if possible) that symmetric submodular functions are non-monotone (excluding constant sub-modular functions). Recall that a submodular function $f : 2^{\Omega} \rightarrow R$ is ...
4
votes
2answers
136 views

class 1 vs class 2 in regular graphs

Vizing's theorem states that a graph can be edge-colored in either $\Delta$ or $\Delta+1$ colors, where $\Delta$ is the maximum degree of the graph. A graph with edge chromatic number equal to ...
3
votes
0answers
146 views

Hitting edges in graphs at random and let them die with honor

Let $G=(V,E)$ be a finite simple 2-connected graph. Let $B\subseteq E$ be a set of bad edges of size $k:=|B|$. For each edge $e\in E$ we toss a fair coin ($p=1/2$) and if the outcome is head, we hit ...
1
vote
1answer
178 views

Upper bound on the number of vertex transitive graphs

Is there a known upper bound on the number of vertex transitive graphs on $n$ vertices?
6
votes
0answers
163 views

Permutation Group Question

A question about permutation groups: I wonder if someone who is expert in permutation group theory could answer the following question. Let $x \in S_n$ (the symmetric group) be an involution which ...
1
vote
0answers
80 views

On 'Very Movable' Geometric Configurations (Configurations with a large degree of freedom)

Let $C$ be an $(n_r, b_k)$ combinatorial configuration that admits a geometric realization in the plane. I'm interested in the maximum number of points/lines $M$ of $C$ we can place in general ...
4
votes
2answers
134 views

Details of generation programs supplied with nauty

The program nauty comes with gtools which contains, among others, several generation programs like geng, genbg, ... I was ...
2
votes
3answers
204 views

Regular graphs whose neighbourhoods induce matchings

Studying some problem I've arrived to the following notion. Let a $2r$-regular graph $G$ be called neighbour-matching if $N(v) = rK_2.$ In other words, the neighbourhood of any vertex induces a ...
1
vote
4answers
164 views

Counting simple 4-cycles in an undirected graph [closed]

I'm looking for an algorithm which just counts the number of simple and distinct 4-cycles in an undirected graph labelled with integer keys. I don't need it to be optimal because I only have to use it ...
-2
votes
1answer
144 views

the number of connected components [closed]

I am finding a solution of the following problem. I would like you to give a short proof. Let A be the adjacency matrix of a d-regular graph G. Prove that d is an eigenvalue of A with multiplicity at ...
1
vote
1answer
116 views

Upper-bound for maximal-cliques on perfect graphs

It has been proved by Moon and Moser in 1965 that any finite simple graph has at most $3^{|V|/3}$ maximal cliques. Still, some hereditary classes of graphs have very few maximal cliques in comparison ...
4
votes
1answer
117 views

Epidemic threshold

Need some help / ideas to proceed. Stuck for a while on this. In the literature of epidemic theory, it is found that the epidemic threshold is $1/\lambda_{max}(A)$ where $\lambda_{max}(A)$ is the ...
3
votes
1answer
114 views

Have chordal outerplanar graphs been studied before?

Recall a graph is chordal if it contains no induced cycle of length 4 or more, and outerplanar if it has a crossing-free embedding in the plane such that all vertices are on the same face. While ...
0
votes
0answers
87 views

Articles on (Strongly Regular) Graphs and Covering Arrays / Covering Designs?

In their book "Algebraic Graph Theory" Godsil and Royle mention the connection of strongly regular graphs with latin squares and thus Orthogonal Arrays (Chapter 10.4). There seems not to be much ...
6
votes
1answer
130 views

A family of skew-symmetric matrices corresponding to cycles in graphs

When investigating loops in Markov chains I ran into the following observation. A cycle in a graph $G$ with $n$ vertices may be represented by a matrix $\Gamma \in \mathbb R^{n \times n}$ having the ...
0
votes
0answers
65 views

Existence of a sequence of (almost) Moore irregular graphs embedded on closed surfaces

Let $S_{g}$ denote the genus $g$ closed orientable surface. I'm interested in disproving the existence of a certain configuration of simple closed curves on $S_{g}$. I'd be happy to go into more ...
8
votes
3answers
286 views

Characteristic polynomials of trees and E8

In thinking about constructing manifolds via surgery or plumbing, the following combinatorial problem comes up: If T is a tree with adjacency matrix A and I is the identity matrix of the same order, ...
3
votes
1answer
167 views

Equivalence of Hadamard Graph and Hadamard Matrix

I'm reading Distance Regular Graphs by Brouwer, Cohen, and Neumaier. In section 1.8, they explained Hadamard graphs. Conversion from a Hadamard Matrix into a Hadamard Graph An $n$-Hadamard graph $G$ ...
5
votes
2answers
148 views

Reflexive (hyperbolic) graphs

Is there an effective description of the graphs such that exactly one eigenvalue (of the conventional adjacency matrix) is $>2$ whereas all others are $\le2$? By "effective" I mean something ...
0
votes
0answers
57 views

Lemma about complete subgraphs of r-parite graphs by Bollobás

Lemma connected with counting z(m,n;s,t): Let $m, \, n,\, s, \, t, \, r, \, k$ be integers, $0 \leqslant s \leqslant m$, $0\leqslant t \leqslant n$,\ $0\leqslant k$, $ 0\leqslant r \leqslant m$ and ...
3
votes
2answers
204 views

spectrum of an adjacency matrix

The adjacency matrix of a non-oriented connected graph is symmetric, hence its spectrum is real. If the graph is bipartite, then the spectrum of its adjacency matrix is symmetric about 0. A few ...
4
votes
1answer
144 views

Universal graphs on higher cardinals

The Rado graph contains every finite graph as induced subgraph, and its also holds for countable graphs. So it is an universal graph of size $\aleph_0$, which contains all graphs of size $\aleph_0$ as ...
1
vote
1answer
171 views

Counting edges in embeddable CW-complexes in R^3

Using Euler's formula ($V-E+F = 2$ where $V$, $E$ and $F$ are the number of vertices, edges and faces), we can easily count the number of edges in maximal graphs that are embeddable in plane: 3n-6. I ...
15
votes
0answers
206 views

Is the Poset of Graphs Automorphism-free?

For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$. ...
3
votes
0answers
70 views

What is this expander-mixing-type graph property?

Fix $C>0$. I am interested in graphs with the following mixing property: $$\Big|E(S,T)-\frac{1}{2}|S||T|\Big|\leq C\sqrt{|S||T|\max\{|S|,|T|\}}$$ for every disjoint $S,T\subseteq V$. Note that ...
2
votes
1answer
143 views

Regular graphs with $a$ and $b$ Hamiltonian edges

Special case of this question. Let $G$ be $r$-regular Hamiltonian graph. An $a$ edge is an edge which is on every Hamiltonian cycle. A $b$ edge is an edge which is on no Hamiltonian cycle. $a(G)$ ...
5
votes
6answers
396 views

Random planar, bipartite graphs

I have a need to generate random planar graphs none of which have an odd cycle, i.e., bipartite graphs. I know there is a substantial two-decade literature on random planar graphs, little with which I ...
2
votes
1answer
89 views

Subdividing toward a unit distance graph in the plane

I just want to ask, what is the significance of subdividing a graph toward a unit distance graph? I have seen several studies of it but I cannot find what its importance. I mean, like the study of ...
5
votes
1answer
215 views

Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$. Consider the bipartite ...
7
votes
2answers
288 views

Graphs with many edges avoided by Hamiltonian cycles

Let $G$ be a $3$-connected Hamiltonian graph with at least one edge that belongs to each H-cycle of $G$. Some authors (e.g. in the link given here) call such an edge an a-edge and an edge that belongs ...
4
votes
2answers
177 views

Number of unlabelled planar graphs

What are the best known bounds on the number of non-isomorphic (unlabelled) planar graphs on $n$ vertices? Is there a simple proof that this number is at most exponential in $n$?
1
vote
1answer
120 views

Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of ...
6
votes
0answers
277 views

the length of paths in a specific graph

Let $n$ be a positive integer and $K$ be the set of all the $2$-elements subsets of $\{1,2,...,n\}$,then $|K|= \binom{n}{2}$. Define $$S=\{P\subseteq K:\bigcup_{I\in P}I=\{1,2,...,n\}\}.$$ For any ...
1
vote
1answer
196 views

Is this Graph parameter known?

Let $\lambda(G)$ denote the edge-connectivity of $G$. Consider the following parameter: $\rho(G) = \max_{X \subset V(G)} \min(\lambda(G[X]), \lambda(G[V(G) - X]))$ Has this parameter been studied? ...
4
votes
1answer
106 views

Graph Verification Problem

Does anyone know whether the following problem has been solved or has an easy solution? Given a graph $(V,E)$, two subsets of the vertices $U_1=\{u_1, \dots, u_r \}, U_2=\{v_1, \dots, v_s \} \subset ...
2
votes
0answers
46 views

Minimal set of 2-2 Pachner move null sequences on a (nonplanar) trivalent graph?

A "null sequence" is of course a sequence of Pachner moves (inside a closed area) that doesn't change the trivalent graph. E.g. doing the same Pachner move twice (leads to orthogonality of 6j symbols) ...
5
votes
0answers
106 views

Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph

According to a conjecture: Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common. Equivalent statement here Main question: ...
12
votes
3answers
600 views

Are infinite planar graphs still 4-colorable?

Imagine you have a finite number of "sites" $S$ in the positive quadrant of the integer lattice $\mathbb{Z}^2$, and from each site $s \in S$, one connects $s$ to every lattice point to which it has a ...
2
votes
1answer
146 views

About an equivalent to Tutte's 5-flow Conjecture

A while back I remember reading that F. Jaeger proved that Tutte's $5$-flow conjecture is equivalent to a statement about the co-planarity of a certain set of points in some euclidean space. But I ...
3
votes
2answers
242 views

Which directed graphs have a normal adjacency matrix?

I am working on a problem in matrix analysis and I am looking for certain types of normal matrices. I suspect that these "special" normal matrices arise as adjacency matrices of certain graphs. My ...
3
votes
2answers
222 views

Can the Vertices of cubic graph be partitioned into and induced cycle and a forest?

Let $G$ be a $2$-connected $3$-regular graph. Can $V(G)$ be partitioned into $V_1$ and $V_2$ where $G[V_1]$(the induced subgraph on $V_1$) is a cycle of $G$ and $G[V_2]$ is a forest (Acyclic ...
2
votes
1answer
136 views

Is the set of edge of a cubic graph the union of a cycle and and an Acyclic graph?

Let $G$ be a $2$-connected $3$-regular graph. Is it true that $E(G) = E_1 \cup E_2$ where $G[E_1]$(the induced subgraph on $E_1$) is a cycle of $G$ and $G[E_2]$ is a forest (Acyclic subgraph) of $G$? ...
2
votes
0answers
78 views

Counting regular Hypergraphs

The problem of counting regular graphs on $n$ vertices is notoriously hard. It seems like counting regular hypergraphs on $n$ vertices should be much easier (I am placing no uniformity condition). ...
0
votes
1answer
77 views

Topological Irreducible graphs for the projective plane

I learned that there are 103 topological irreducible graphs for the projective plane but I am unable to find examples of said graphs. I am unsure of how to find them on my own and I would like to see ...
4
votes
1answer
105 views

Counting the number of $(d_v,d_c)$ regular bipartite graphs

I am trying to count the number of $(d_v,d_c)$ regular bipartite graphs. To be specific, let $n,m,d_v,d_c$ be positive integers such that $$n\times d_v=m\times d_c.$$ Then, what is the number of ...
2
votes
1answer
179 views

Coloring of subgraphs of G^n

Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , ...
3
votes
1answer
201 views

Expected Value for a Connected Graph

Consider a connected graph of N nodes. Assign randomly to each node a distinct number from 1 to N. For each node consider the maximum adjacent value or itself if all adjacent values are smaller. ...
1
vote
0answers
125 views

A connection between nonplanar complete graphs and the alternating group?

I didn't get any response on MSE so I though I'd give this a try here (my question on MSE). I went to an undergrad's senior honors thesis presentation a while ago. She was discussing crossing numbers ...