# Questions tagged [graph-theory]

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, topological-graph-theory, random-graphs, graph-colorings and several others.

4,823 questions
Filter by
Sorted by
Tagged with
27 views

• 1,952
356 views

### Is there a program implementation for generating all non-isomorphic graphs with a given degree sequence?

I know the following problem is famous: For a given degree sequence $L$ that is graphic, find an (efficient) algorithm to generate all of the nonisomorphic realizations of $L$. This algorithm is ...
• 855
55 views

### Research on lower bounds of sphericity of a graph

I am looking for references that address lower bounds on the "sphericity" of a graph. For a finite point set in Euclidean $n$-space, if we connect each pair of points by a line segment ...
331 views

### Six people standing on earth

Consider 6 people $p_i$, $i=1,\dots 6$, standing on a sphere $S^2$. We label the positions of these people by $p_i$ again. Suppose no pair of these points $p_i$ are antipodal. At each point $p_i$ ...
• 311
40 views
+100

### What is the analogue of a Block-Cut Tree Decomposition in directed graphs?

Let $G$ be a connected, undirected graph. We define a block $B$ to be a maximal $2$-connected induced subgraph in $G$. It is easy to see that any two distinct blocks are either disjoint or overlap at ...
• 300
1 vote
136 views

### Categories associated to digraphs

Let's take a directed graph, or a digraph, $G=(V,E)$ given by a finite set of vertices $V$ and a finite set of edges $E$. We can assume that pairs of vertices can have parallel edges between them and ...
130 views

### What is this Ramsey problem

Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ ...
• 1,921
79 views

### How to find a specific clique cover set?

Let $G(\mathcal{V},\mathcal{E})$ be a graph with vertex set $\mathcal{V}$ and edge set $\mathcal{E}$. Also, non-negative weights $w_i$ are assigned to each vertex $i\in\{1,\ldots,n\}$. Suppose the ...
• 63
39 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 ...
• 199
38 views

### Number of balanced-parentheses sequences on $2n$ bits as $n$ grows large [migrated]

The motivation to consider the sequences below comes from an efficient way to represent trees on $n$ nodes using $2n$ bits. Let $n\in\mathbb{N}$ be a positive integer. Let us call $s\in\{0,1\}^{2n}$ a ...
165 views

### Covering discrete triangle with generalized knight jumps

Consider for $n\in\mathbb{N}, n\geq 6$ the discrete triangle $\nabla=\{(i,j)\in \{1,\ldots,n-1\}^2 \mid j\leq n-i\}$. This is basically the lower "half" of a chess board if you cut it along ...
61 views

• 402
214 views

### Hoffman singleton conjecture

So I am currently working on the Hoffman singleton conjecture. For those who do not know this conjecture, it is asking whether there exists a 57-regular, girth 5 graph with $57^2+1$ vertices. While ...
• 233
125 views

39 views

### Complete characterization of graphs with cubicity $\leq 2$

Are there any known complete characterizations of graphs with cubicity $= 2$? (Graphs with cubicity $2$ are those which can be represented as the intersection graphs of squares in $\mathbb{R}^2$) For ...
• 121
112 views

165 views

### Lovasz's conjecture for dihedral Cayley graphs

Background: A tantalizing conjecture of Lovasz is the following: Let $G$ be a (finite) connected vertex-transitive graph. Then $G$ contains a Hamiltonian cycle or is one of $5$ counter-examples. (...
• 1,921
1 vote
52 views

### Complexity of EFL coloring of a set of lines

Let $M$ be a set of straight lines. Define an EFL coloring of $M$ with $k$ colors as a function $f : P(M) \rightarrow \{ 1,2,\dots,k \}$, such that if two intersection points $p_1, p_2$ belong to the ...
200 views

### Dual polyhedra and electric circuits

Good morning, I hope this question is not too far out of the scope of the forum. I am posting it here because this doesn't seem to be a very standard problem. Yesterday we were calculating the ...
• 413
146 views

• 143
233 views

### Did these graphs pop up somewhere?

Please let me know if the following graphs popped up in some problems. Each of these graphs is described by 5 integers $n_1\geqslant k_1$, $n_2\geqslant k_2$, $l\geqslant 0$. We take two complete ...
• 40.5k
119 views

### Representing graphs by $\text{Hom}$-graphs

Let $G, H$ be simple, undirected graphs. A graph homomorphism from $G$ to $H$ is a map $f:V(G)\to V(H)$ such that whenever $\{v,w\}\in E(G)$ then $\{f(v), f(w)\}\in E(H)$. Let $\text{Hom}(G,H)$ be the ...
100 views

### Completing subcubic trees to cubic graphs

A graph theory question: For given girth g, does there exist $n_0(g)$ such that any tree $T$ of even order $n \geq n_0(g)$ and maximum degree $\Delta(T) \leq 3$ can be completed to a cubic graph with ...
• 131
130 views

### Impact of the global cost function (weighting) to Betweenness Centrality distribution

I have a graph whose edges have all a weight of 1. In my particular case computing the Betweenness centrality by counting shortest paths between all pairs results ...
146 views

### Name for a chain-like graph

Is there a name for graphs of the following type? Namely, it has an integer function $\ell$ on the set of the vertex set such that $v$ is adjacent to $w$ if and only if $$|\ell(v)-\ell(w)|\le 1.$$ ...
• 40.5k
435 views

### Turán's theorem for cosets of groups

Let $G$ be a finite group, $G',H$ be its subgroups and $H'=G'\cap H$. For each $g\in G$, we create a map $f_g:G'/H'\rightarrow G/H: aH'\rightarrow gaH$. It's easy to see that the map is well defined ...
• 1,017
1 vote
81 views

### Finding $k$ active elements by evaluating the "any-operator" of subsets of variables

Assume a set $S$ of elements $\{s_1,\dots,s_n\}$, each which has a hidden label 'active' or 'inactive'. Assume there are $m\ll n$ active elements in total. You are allowed to iteratively perform a ...
This question is posted from StackExchange since it received no answer there. Let $f(n, e)$ be the number of triangle-free graphs on $n$ vertices and $e$ edges. From empirical evidence, I am motivated ...