**3**

votes

**0**answers

161 views

### vertex transitive and Cayley graphs

(all the graphs alluded to below are finite).
Suppose I gave you a graph, and asked you whether it was vertex-transitive. How hard is that algorithmically?
The second question is: suppose I gave you ...

**4**

votes

**1**answer

180 views

### Reference request: “unoriented composition” in generalized categories

I'm looking for a generalized notion of category (really of symmetric multicategory) which, roughly speaking, doesn't make a distinction between sources and targets. Each "morphism" in such a category ...

**8**

votes

**1**answer

321 views

### A combinatorial problem concerned with logic circuits

Consider a logic circuit with two-bit gates only. The length of each gate is the number of bit lines that the gate crosses. How hard is to compute the maximum length for a given circuit? Notice that ...

**4**

votes

**1**answer

365 views

### Genus of a graph

Let $G$ is a simple undirected graph. Suppose $G$ has two subgraphs $G_1$ and $G_2$, such that $E(G_1)\cap E(G_2) =\emptyset$ ($E(G_i)$, stand for the set of edges of $G_i$). Then is it true that ...

**3**

votes

**2**answers

334 views

### A structure of the group of automorphisms of an infinite binary tree

My friend asked me to ask his question here. Where he can find (a paper or a book) containing a complete description (with the proof) of a structure of the group of automorphisms of an infinite binary ...

**3**

votes

**2**answers

196 views

### Making a graph claw-free by adding as few edges as possible

Independent set is polynomial in claw-free graphs,
so I am wondering if this can approximate independent set.
By adding enough edges to $G$ and gets claw-free $G'$.
IS in $G'$ is IS in $G$, so this ...

**0**

votes

**1**answer

111 views

### Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$).
The cost to send $x$ unit of flow through edge $e_i$ is defined ...

**2**

votes

**0**answers

88 views

### Is there an universal (dis)similarity measure between two structures?

I'm always wondering is there an universal (dis)similarity measure
between two structures (let's say between two undirected simple
graphs)? I mean, not "the measure with universal parameter that we
...

**4**

votes

**2**answers

218 views

### Cubic graphs decompositions

There are many interesting computational problems related to connected cubic graph decomposition. For instance, decomposition of cubic graph into a perfect matching and a connected 2-factor ...

**0**

votes

**0**answers

160 views

### What is the number of connected subgraphs with $n$ vertices of a labelled connected simple graph with $n$ vertices?

Suppose $G$ is a connected simple labeled graph. Let $n$, $e$, and $k$ be its number of vertices, edges, and the upper bound of the degree of a vertex, respectively. How many connected sub-graphs ...

**2**

votes

**0**answers

110 views

### Partitioning a cubic graph into two induced cycles of equal order

I am aware that deciding the existence of a partition of the vertices of a connected graph $G(V, E)$ into two induced cycles is $NP$-complete(Theorem 2). Induced cycle is a cycle without any chord ...

**6**

votes

**1**answer

130 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

**0**answers

50 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

**1**answer

56 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

**2**answers

147 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

**0**answers

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

**2**

votes

**1**answer

197 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

**0**answers

201 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

**0**answers

89 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

**2**answers

139 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

**3**answers

207 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

**4**answers

246 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

**1**answer

241 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

**1**answer

127 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

**1**answer

124 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

**1**answer

119 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

**0**answers

89 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

**1**answer

147 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

**0**answers

67 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

**3**answers

299 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

**1**answer

198 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

**2**answers

155 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

**0**answers

59 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

**2**answers

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

**5**

votes

**2**answers

220 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

**1**answer

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

**16**

votes

**0**answers

225 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

**0**answers

74 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

**1**answer

151 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

**6**answers

408 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

**1**answer

95 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

**1**answer

297 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

**2**answers

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

**5**

votes

**2**answers

204 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

**1**answer

146 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

**0**answers

284 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

**1**answer

202 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

**1**answer

109 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

**0**answers

51 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

**0**answers

113 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:
...