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

5
votes
3answers
261 views

How hard is it to determine if a weighted graph can be isometrically embedded in R^3?

Consider a graph $G$ with nonnegative edge weights. Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight? ...
0
votes
0answers
52 views

A particular method of removing edges from strong di-graphs

I have been mulling over a little puzzle I gave myself involving a particular type of iterative removal of edges from a digraph and I'm stuck -- thought I'd consult experts. Start with an ...
1
vote
0answers
30 views

Harmonic Bergman spaces on graphs

Harmonic Bergman spaces on Euclidean domains are a set of harmonic functions on a domain that are from $L^{p}$ of that domain. I tried to find something on harmonic Bergman spaces on graphs because we ...
3
votes
0answers
162 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
1answer
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
1answer
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
1answer
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
2answers
336 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
2answers
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
1answer
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
0answers
89 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
2answers
219 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
0answers
161 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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
0answers
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
1answer
198 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
202 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
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
2answers
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
3answers
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
4answers
248 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
245 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
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
1answer
126 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
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
0answers
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
1answer
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
0answers
68 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
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
1answer
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
2answers
156 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
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
2answers
330 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
2answers
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
1answer
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
0answers
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
0answers
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
1answer
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
6answers
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
1answer
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
1answer
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
2answers
340 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
2answers
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
1answer
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
0answers
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
1answer
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? ...