Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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 ...