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

**4**

votes

**0**answers

33 views

### Connected incomparability graph

Let $X$ be a finite set equipped with a partial order. (Not a preorder: $a < b$ implies $b \not< a$.) The corresponding incomparability graph has vertex set $X$ with an edge between two points ...

**-2**

votes

**0**answers

53 views

### Graph with 5 nodes max that fulfils the following [on hold]

i) It should contain exactly four cycles and these should all have length $4$;
ii) Graph should contain a node which has degree $3$;
iii) Graph should contain a subgraph which is a tree that ...

**1**

vote

**1**answer

46 views

### Spatial dimension of a finite graph

If $(X,d)$ is a metric space, we associate with it a simple, undirected graph, called its proximity graph $G(X,d)$ given by $V(G(X,d)) = X$ and $$E(G(X,d)) = \big\{\{x,y\}:x\neq y\in X \text{ and } d(...

**3**

votes

**0**answers

45 views

### Name of a binary matroid coming from the cycle space of a graph

In some of my recent work, I have 'discovered' a binary matroid which I will describe below.
Given a graph $G$, let $H_1(G, \mathbb{Z}/2\mathbb{Z})$ denote the cycle space. This is a vector space ...

**2**

votes

**0**answers

21 views

### Generating complete sets of representatives for the strong contentedness equivalency on the tensor product of strongly connected digraphs

Given any $n\geq 2$ strongly connected digraphs $\small D_1,D_2,\ldots D_n$, if we let $\small T=D_1\otimes D_2\otimes\cdots\otimes D_n$ be their tensor product then by definition we can write $T=(X,R)...

**1**

vote

**1**answer

58 views

### How many graphs of order n, maximum degree k, and maximum diameter d exist?

The total number of simple undirected graphs of order $n$ is
$\sum\limits_{i = 0}^{\frac{n(n-1)}{2}}{\binom{\frac{n(n-1)}{2}}{i}} = 2^{\frac{n(n-1)}{2}}$.
What is the number of simple undirected ...

**1**

vote

**1**answer

35 views

### Does $G$ with $\delta(G)\geq \aleph_0$ contain $k$-regular sub-edge-sets?

Let $G=(V,E)$ be an infinite, simple, undirected graph, such that for all $v\in V$ we have $\text{deg}(v) \geq \aleph_0$. Given an integer $k\geq 1$, is there always $E^{(k)}\subseteq E$ such that $(V,...

**1**

vote

**1**answer

48 views

### Some questions about a family of regular undirected graphs

Let $S$ be the regular n-dimensional simplex. We create a graph of where the vertices are m-faces and two vertices are connected if there exist a common (m-1)-face which they share.
Then the number of ...

**-4**

votes

**0**answers

33 views

### Subdivision of a graph [closed]

Show that subdivision of a graph X is edge transitive if and only if X is arc transitive and is vertex transitive if and only if X is a union of cycles of the same length?
I don't have any idea about ...

**-2**

votes

**0**answers

88 views

### Summary of how mathematicians have been able to reduce the number of maps to check in the Four Color theorem [closed]

I'm doing an essay on the effectiveness of the ability of computers to help prove the Four Color Theorem. I've looked a lot online but I have not found a good resource specifically answering how ...

**0**

votes

**0**answers

74 views

### Find a graph when given length-k paths?

I have an undirected connected graph $G$ and I have a matrix $S^{(k)}$ were $S^{(k)}_{i,j}=1$ if there is a length-$k$ path between $i$ and $j$ and 0 otherwise. Now, $S^{(1)}$ is then simply the ...

**0**

votes

**1**answer

45 views

### On the formal definition of mesh or region for a planar graph

A graphical representation of a planar graph divides the plane into regions or meshes (as they are called in certain applications, e.g. in circuit theory).
Yes, the above fact is intuitive, but what ...

**2**

votes

**0**answers

34 views

### Reference on generalization of plane graph duality between bonds and simple cycles

Let $G$ be a plane graph, and $G^*$ its dual. Among the $k$ partitions of the nodes of $G$, I'll call the connected k-partitions those such that each block of nodes of the partition induces a ...

**0**

votes

**2**answers

106 views

### Vertex Connectivity of the Hypercube [closed]

I am revising my lecture notes about connectivity, but I am stuck regarding proof of $κ(Q_d) = d$ Then I took a look of the proof by induction in D. West's book. For $d\leq1$, $Q_d$ is a clique with $...

**7**

votes

**1**answer

107 views

### Going up of an amalgamated decomposition of a subgroup of finite index

Let $G$ be a finitely presented group and H a subgroup of index $n$ in $G$. Suppose that H has a non-trivial decomposition as amalgamated product, say $H = A \ast_U B$. I am wondering about the ...

**3**

votes

**1**answer

135 views

### existence of a certain subset of vertices in a graph

Take an undirected graph $G=(V,E)$. For any subset $M\subseteq V$, we define ${\rm deg}_M(v)=|\{k\in M:(v,k)\in E\}|$, namely, the number of neighbors of $v$ in $M$.
Is it true that, there exists a ...

**0**

votes

**2**answers

85 views

### Does Max Flow produce uniform results? [closed]

I am interested in using Max Flow algorithm. I want to simulate transfer of quantity. Anyway, I am unsure of some thing.
Does Max Flow algorithm produce uniformly distributed max flow?
I have ...

**0**

votes

**1**answer

60 views

### Minimizing the set of “wrong” edges in $K_\omega$ with $\{0,1\}$-weights

For any set $X$, let $[X]^2 = \big\{\{x,y\}:x\neq y\in X\big\}$.
Let $f:[\omega]^2\to\{0,1\}$ be a function. The principal goal is to find a partition of $\omega$ such that if $m\neq n\in \omega$ ...

**1**

vote

**0**answers

42 views

### Generate all connected non-isomorphic graphs of n vertices modulo local complementation?

I'd like to generate a list of all simple, connected, undirected graphs of $n$ vertices, modulo standard graph isomorphism, and modulo local complementation, which is the following operation: for a ...

**1**

vote

**0**answers

58 views

### matching two positive-semidefinite matrices

Let $M_1$ and $M_2$ be two real positive-semidefinite matrices. Is there any algorithm to compute a permutation matrix $P$ to minimize $\| M_1-PM_2P^T \|_F^2$ or equivalently to maximize $trace(...

**1**

vote

**0**answers

70 views

### What is intuitive perception of $T_{\alpha_1} \circ T_{\alpha_2} \circ … \circ T_{\alpha_M} $ in graph domain?

if $G(V,E,W)$ be a weighted graph and $\vert V \vert =N $. for any vertex $i \in \lbrace 1,2,...,,N \rbrace $ define a generalized translation operator $T_i:\mathbb{R}^N \to \mathbb{R}^N $via ...

**10**

votes

**1**answer

259 views

### An upper bound for the largest Laplacian eigenvalue of a graph in terms of its diameter

Let $G$ be a simple graph with $n$ vertices and $\lambda$ be the largest eigenvalue of its Laplacian operator $L=D-A$. I have some evidence for the following conjecture:
Conjecture: If G has ...

**1**

vote

**0**answers

43 views

### Number of sequences of edges that contain at least one subsequence which is a walk between vertex $i$ and $j$

Typically a walk is defined as a vertex-edge sequence, e.g. $(v_1, e_1, v_2, e_2, v_3)$, but suppose we are working in the undirected simple graph setting. Instead, let's say an edge-sequence $(e_1, ...

**2**

votes

**2**answers

96 views

### Clique Size in “Triangle Regular” Graphs

Let $G(V,E)$ be a connected, simple and undirected graph with the additional constraint, that each edge is contained in the same number $k_T$ of triangles; i.e. that $G$ is regular w.r.t. to that ...

**11**

votes

**0**answers

131 views

### Quantitatively characterizing the failure of the converse of Dirac's theorem

First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.
I am currently in a combinatorics and graph theory class and recently we have ...

**9**

votes

**1**answer

133 views

### Discrete Pin structures

It is clear that an oriented manifold $M^n$ (with dimension $n$) admits spin structures if and only if its second Stiefel-Whitney class $[w^2]\in H^2(M,\mathbb Z_2)$ vanishes. In the construction of ...

**0**

votes

**0**answers

100 views

### Babai Invariant group

A finite group $G$ is called a BI-group if Cay(G, S) ≅ Cay(G,T) for some inverse closed subsets $S$ and $T$ of $G\setminus\{1\}$, then $M_{ν}^{S}=M_{ν}^{T}$ where $M_\nu^S$ denotes the set $\big\{\...

**3**

votes

**1**answer

115 views

### Minimal vertex cover

Definition:
Let $G$ be a graph. A subset $C \subseteq V(G)$ is a vertex cover of
$G$ if for each $e \in E(G)$, $e\cap C \neq \phi$. If $C$ is minimal
with respect to inclusion, then $C$ is called ...

**2**

votes

**1**answer

75 views

### Upper bound on the number of induced subgraphs of the square lattice with all degrees even

An induced subgraph of a graph $G$ is defined by a subset of vertices of $G$ together with all edges in $G$ that connect vertices from the chosen subset.
Consider now an $n\times m$ square lattice. ...

**3**

votes

**1**answer

79 views

### Cliques in Cayley graph on $n$-cycles

Let $S\subset S_n$ be the set of all $n$-cycles. I want to know if the Cayley graph $(S_n,S)$ has large dense subgraphs. I'm expecting it to not have super-polynomial size and $1-o(1)$ dense subgraphs....

**0**

votes

**0**answers

33 views

### Equitable partition

This is in reference to this question:
equitable partitions
Suppose I have this graph enter image description here
whose equitable partition can be taken as $\{1,3,5,7\} ;\{6,2,4,8\}$
But then as ...

**0**

votes

**1**answer

33 views

### Graph with at most 2 degrees of separation between every node, but minimal average degree

Is there a simple way to construct such a graph? For example a fully connected graph obviously has degree of separation between every vertex of 1 but has maximal total degree. If we only wanted to ...

**7**

votes

**1**answer

433 views

### Given any finite relation $R$ what is the cardinality of $\langle R\rangle=\{\underbrace{R\circ R\cdots \circ R}_{n\text{ times}}:n\in\mathbb{N}\}$?

Given any finite relation $R$ if we let $\circ$ denote relation composition and define $R^n=\underbrace{R\circ R\cdots \circ R}_{n\text{ times}}$ then does there exist an explicit formula for the ...

**5**

votes

**0**answers

38 views

### Universal point sets for 1-plane graphs

It is a notorious open problem to find a smallest set of $N$ points that
permit any $n$-vertex planar graph to be drawn in the plane without
crossings, using only those $N$ points as vertices, and ...

**6**

votes

**0**answers

154 views

### A conjecture on the coefficient of a special term in the expansion of the graph polynomial?

Recently, I am interested in the polynomial polynomial of the product of cycles.
Let $G = (V , E)$ be an undirected multi-graph with vertex set $\{1,\cdots,n\}$. The graph polynomial of $G$
is ...

**1**

vote

**1**answer

67 views

### Degree sequence along an Eulerian cycle

I would like to know if there exists a result saying that for a fixed undirected rooted Eulerian graph, up to some permutation, along any Eulerian cycle, there exists a unique sequence of degrees, ...

**3**

votes

**1**answer

69 views

### Typical labelled vs. unlabelled trees properties

Consider two random tree models $T_1(n)$ and $T_2(n)$, chosen equiprobably among labelled and unlabelled trees on $n$ vertices respectively. I'm wondering if there are properties that are vastly more ...

**5**

votes

**1**answer

103 views

### Length minimizing graphs between a finite set of points

Consider a set of $n$ points in the plane. Among all the connected graphs (trees) $T$ in the plane that have these $n$ points among their vertices, I am looking to find one such that the sum of its ...

**3**

votes

**1**answer

60 views

### Optimal Strategies for a “Blind” Graph Coloring Game

By the "blind" graph coloring game I denote the following problem, which is played by two players:
player A has $k<n$ colors at hand to color the $n$ vertices of a graph $G$, but that player has ...

**2**

votes

**0**answers

42 views

### Karp hardness of two cycles which lengths differ by one

Our problem is as follows:
NEARLY-EQUAL-CYCLE-PAIR
Input: An undirected graph $G(V,E)$
Output: YES if there exists $2$ (simple) cycles in $G$ which lengths differ by $1$, otherwise NO
Is ...

**5**

votes

**1**answer

67 views

### What is the complexity of counting Hamiltonian cycles of a graph?

Since deciding whether a graph contains a Hamiltonian cycle is $NP$-complete, the counting problem which counts the number of such cycles of a graph is $NP$-hard.
Is it also $PP$-hard in the sense ...

**-1**

votes

**1**answer

76 views

### Existence of a graph with strong restrictions

Given a maximal degree $k$ and maximal diameter $d$. We identify 3 nodes, $i$, $j$, and $v$. Can an undirected graph exist, such that:
all nodes but $v$ have full degree $k$ ($v$ having a lower ...

**4**

votes

**1**answer

66 views

### Minimum number of vertices in a $k$-chromatic graph of odd girth $g$

The odd girth of a graph $G$ is defined as the minimum length of an odd cycle in $G$. Let $n_g(k)$ denote the minimum number of vertices in a $k$-chromatic graph of odd girth $g$. What are the known ...

**2**

votes

**1**answer

34 views

### Terminology for tree subgraphs where non-neighbouring vertices are not connected by single ambient edges

Suppose $G=(V,E)$ is a connected graph and $T=(V_T, E_T)$ is a subgraph of $G$ that is a tree.
If we further suppose that any pair of vertices $v,w \in V_T$ that are not joined by a single edge in $...

**2**

votes

**0**answers

89 views

### Percolation-type question involving phase transition for graded acyclic directed graph

Let $G$ be an acyclic directed graph with $MN$ vertices arranged into $M$ generations of $N$ vertices each. We stipulate that edges may only go from generation $j$ to generation $j+1$, so there are $(...

**1**

vote

**1**answer

60 views

### Algorithm for cliques in weighted graph

Is there a known algorithm (besides brute force) for the following problem:
We have given an edge-weighted complete graph $G$ and a finite set of natural numbers $A = \lbrace n_1,\ldots,n_k \rbrace$ (...

**3**

votes

**0**answers

62 views

### Maximum spanning paths in a graph

Is there any research on the question of finding a spanning subgraph in the form of a collection of independent paths with a maximum number of edges? If the paths are simply edges we have the maximum ...

**7**

votes

**1**answer

162 views

### Counting spanning trees of a planar graph

I know through Kirchoff's Theorem, one can calculate the number of spanning trees via the determinant of a Laplacian. This has complexity $O(N^{2.373}$). I was wondering if anyone was aware of a ...

**1**

vote

**0**answers

33 views

### Tight upper and lower bounds for unbalanced left-regular expander graphs

I am interested in finding the best expansion parameters for unbalanced left-regular expander graphs.
Specifically, fix $\delta\in(0,1/2)$, and a positive integer $d$. Let us call a bipartite graph $\...

**8**

votes

**0**answers

117 views

### Minimal number of colours in distinguishing colouring of biconnected graphs

A colouring of edges of a graph is distingushing if no non-identity automorphism of the graph preserves this colouring.
Problem. Is it true that each biconnected graph possesses a distinguishing ...