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

0
votes
2answers
112 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
129 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 ...
4
votes
1answer
144 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
70 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
46 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
59 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
74 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
274 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
1answer
81 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
105 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
143 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
142 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 ...
-1
votes
0answers
101 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
117 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
84 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
81 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
41 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
455 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
41 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
160 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
68 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
73 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
109 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
63 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 ...
3
votes
0answers
43 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 ...
6
votes
1answer
69 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
77 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
75 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
35 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
63 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
173 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
34 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
119 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 ...
4
votes
4answers
198 views

Bijective operations on finite simple graphs

Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices. I am interested in specific bijective maps $\mathcal G_n\to\mathcal G_n$, defined for all $n$. An ...
5
votes
0answers
67 views

Extending colouring of graphs using small number of colours

Conjecture (Csóka-Lippner-Pikhurko). If $G$ is a graph with each vertex of degree $\le d$ with at most $d-1$ pendant edges properly coloured, then this pre-colouring can be extended to all edges of $G$...
0
votes
0answers
46 views

How many possible choices are there to make a ternary tree equal height by inserting nodes?

Suppose $T$ is a ternary tree with $s$ nodes. Here, a tree is ternary if every node in the tree is either a leaf node (with no child) or a non-leaf node with exactly three child. See below for a ...
6
votes
0answers
103 views

Does the problem of recognizing 3DORG-graphs have polynomial complexity?

A 2DORG is the intersection graph of a finite family of rays directed $\to$ or $\uparrow$ in the plane. Such graphs can be recognized effectively (Felsner et al.). A 3DORG is the intersection graph of ...
5
votes
1answer
237 views

Are Gray codes in $\{0,1\}^n$ isomorphic?

Let $n\in\mathbb{N}$ be a positive integer. Two elements of $\{0,1\}^n$ form an edge if and only if their Hamming distance equals $1$. It is known that $\{0,1\}^n$ endowed with this graph structure ...
2
votes
1answer
132 views

non-backtracking random walk in regular (finite) graphs

I know that many things are known when dealing with random walks on a finite (or even infinite) graph: mixing time, returns to origin, etc. All is based in the use of the Markovian property of such a ...
4
votes
1answer
143 views

Component properties in Euclidean graphs with distance threshold

In the context of Euclidean graphs with vertices randomly embedded in either a 2D plane (for instance square with length $L$) or in 3D (similarly, cube of side $L$), where an edge between two given ...
1
vote
0answers
29 views

Weak convexity in graphs

I asked the following question in MathStackExchange, but I did not get any answer, and I think that this might be the appropriate venue for the question. As we know, a finite undirected graph ...
0
votes
1answer
67 views

Graphs represented by a subset of a metric space

Let $(X,d)$ be a metric space, and suppose $S\subseteq X$ is a finite subset in which all pairwise distances are distinct (formal definition here). If $x\in S$ and $k$ is a non-negative integer with $...
1
vote
0answers
46 views

Single source shortest path over non-commutative finite idempotent semiring in Cartesian product

Let $G$ be a Cartesian product of two arbitrary directed weighted graphs $M$ and $N$. The weights are from a non-commutative finite idempotent semiring. Do there exist advanced results on the single ...
3
votes
2answers
339 views

Number of self avoiding paths on a grid graph?

Let $G$ be an $n \times n$ grid graph. Is there anything known about the asymptotic growth rate of the number of self avoiding paths from $(0,0)$ to $(n,b)$ (from the lower left corner to some ...
7
votes
1answer
118 views

equidistributed parameters on graphs

Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices. I wonder whether there are any 'interesting' combinatorial parameters $a,b: \mathcal G_n\to \mathbb ...
2
votes
2answers
263 views

Laplacian of an infinite graph and connected components

For a finite graph with undirected, unweighted edges, a well-known result is that the dimension of the null space of the Laplacian matrix gives the number of connected components. Does this result ...