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.
5,165
questions
3
votes
1
answer
252
views
Sums over products over short paths in an expander graph
Let $\Gamma=(V,E)$ be an undirected graph of degree $d$. (Say $d$ is a large constant and the number of vertices $n=|V|$ is much larger.) Let $W_0$ be the space of functions $f:V\to \mathbb{C}$ with ...
- 19.4k
3
votes
1
answer
194
views
Is it possible to improve the weight of perfect bipartite matchings faster than with Bellman-Ford?
If $G\left(A\cup B,\ E=\lbrace\lbrace a, b\rbrace\,|\, a\in A,\, b\in B\rbrace\right)$ is a weighted bipartite graph and $M_0$ an initial perfect matching, then the optimality of $M_0$ can be verified ...
- 12.7k
3
votes
1
answer
155
views
Traces and closed walks that do not close before their time
Let $A$ be the adjacency matrix of a graph. Then, as is well-known and trivial to show, $\mathrm{Tr} A^k$ equals the number of closed walks of length $k$.
Is there a similar way to express (a) the ...
- 19.4k
3
votes
1
answer
145
views
Structure of boundary labelling in Sperner‘s Lemma
Consider a triangulated polygon in the 2-dimensional plane, where each vertex is labelled green, blue, or orange. Sperner's Lemma asserts that a fully-colored triangle exists in the triangulation, if ...
- 6,787
3
votes
1
answer
214
views
Unique maximum degree in tournament
Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) Let $p(n)$ denote ...
- 1,199
3
votes
1
answer
230
views
Is following function a metric on the set of isomorphism classes of graphs with countably many vertices?
Suppose $\Gamma_1(V_1, E_1)$ and $\Gamma_2(V_2, E_2)$ are simple graphs with countably many vertices. And suppose $A_1$ and $A_2$ are initially empty sets. Suppose two players play the following game: ...
- 2,618
3
votes
1
answer
141
views
Eigenfunctions adjacency operator on infinite graph in $l^2$
Let $\Gamma$ be an infinite (connected) graph without edges going from a vertex to itself (though it might have multi-edges). Let us suppose that $\Gamma$ has finite valence.
Is there always a ...
- 627
3
votes
1
answer
171
views
Edge coloring graphs is in P?
It is known that there exist polynomial time algorithm to approximate the Lovasz number or the supremum of Shannon capacity of graphs.
By Vizing's theorem, the graph $G$ has only two chromatic ...
- 2,027
3
votes
1
answer
62
views
Sum-balanceable finite graphs
Let $G=(V,E)$ be a finite simple, undirected graph. Given $f:V\to \mathbb{Z}$ we define the neighborhood
sum function $\mathrm{nsum}_f:V\to\mathbb{Z}$ by setting
$\mathrm{nsum}_f(v) = \sum\{f(w):w\...
- 45.5k
3
votes
1
answer
93
views
Induced subgraphs of $\text{Exp}(G, K_2)$
If $G, H$ are simple, undirected graphs, we define the exponential graph $\text{Exp}(G,H)$ to be the following graph:
the vertex set is the set of all maps $f:V(G)\to V(H)$
two maps $f\neq g: V(G)\to ...
- 45.5k
3
votes
1
answer
123
views
Deleting vertex decomposes graph
Given is a connected graph with undirected edges such that deleting any vertex decomposes the graph into $\le k$ components, for some $k\ge 2$. Is it true that the graph has a spanning tree with ...
- 95
3
votes
1
answer
94
views
Generalized digraph homomorphisms and graph cores
Given any digraphs $G$ and $H$ we say a surjection $f:V(G)\to V(H)$ reduces $G$ to $H$ if and only if it satisfies $(u,v)\in E(G)\iff (f(u),f(v))\in E(H)$. Where if there exists at least one ...
- 2,506
3
votes
1
answer
195
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 ...
3
votes
1
answer
196
views
Name and information about this graph
A certain family of graphs crossed my way while performing some quantum mechanics calculations, and I am very curious whether they have been studied in mathematics before in a different context.
Also ...
- 155
3
votes
1
answer
284
views
Expected spectral radius for a sparse Erdős-Rényi binary matrix with a certain density
Let $A$ be an $n \times n$ sparse matrix generated via the Erdős-Rényi method. Here, "sparse" means that $\|A\|_F = O(n)$. I am interested in the relationship between the expectation $\mathbb E(\rho(A)...
- 159
3
votes
1
answer
224
views
vertex arboricity and chromatic number of triangle-free graphs
For a (finite and simple) graph $G=(V,E)$, the vertex arboricity, $va(G)$ of $G$ is defined to be the least integer $d$ such that the vertex set of $G$ has a partition $V=V_1\cup V_2\cup \ldots \cup ...
- 61
3
votes
2
answers
128
views
Connected weakly initial graph on $\kappa$ points
Is there a cardinal $\kappa$ and a connected simple, undirected graph $G^* = (\kappa, E^*)$ such that whenever $G = (\kappa, E)$ is a connected graph, there is a graph homomorphism $f:G^*\to G$?
EDIT....
- 45.5k
3
votes
2
answers
176
views
Coloring hypergraphs with no singleton intersections
Let $H=(V,E)$ be a hypergraph. If $\kappa>0$ is a cardinal, we say the hypergraph $H$ is $\kappa$-chromatic if there is a function $c:V\to\kappa$ such that for all $e\in E$ the restriction $c|_e$ ...
- 45.5k
3
votes
1
answer
1k
views
Finding the farthest point from a set of other points
I have a set of nodes in a very large graph which I call Cluster Points. I also have for each point in the graph, the distance from each point in the Cluster point set.
For example: ...
- 133
3
votes
1
answer
254
views
Commutative graph product with multiplicative independence number?
Given two graphs $G,H$ is there a product $\star$ such that 1. and 2. holds where $\alpha$ refers to independence number?
$$\alpha(G\star H)=\alpha(G)\alpha(H)=\alpha(H\star G)$$
$$G\star H\cong H\...
- 13.7k
3
votes
1
answer
318
views
Inferring tree graph from distance matrix
Given a $n$x$n$ distance matrix of some undirected weighted tree graph, is it possible to infer the underlying tree and its edge weights?
For example, suppose we are given the following distance ...
- 41
3
votes
1
answer
362
views
Domination number and chromatic number
Let $G=(V,E)$ be a finite, simple, undirected graph. A dominating set is a set $D\subseteq V$ such that for all $v\in V\setminus D$ there is $d\in D$ such that $\{v,d\}\in E$. The dominating number $\...
- 45.5k
3
votes
1
answer
815
views
Is transitive reduction for a direct acyclic graph really unique? [closed]
According to Wikipedia, "If a given graph is a finite directed acyclic graph, its transitive reduction is unique"
Here is what I think might be a counter-example:
Imagine a diamond-shaped DAG where
...
- 133
3
votes
1
answer
146
views
A modified bipartite assignment problem
Consider the following optimization problem. I have $n$ advisors and $dn$ students. I want to assign each student an advisor so that each advisor has exactly $d$ students. Each advisor/student pair ...
- 1,440
3
votes
1
answer
123
views
A possible GI isomorphic problem
Here I try to seek if restricting the structure of permutations would still keep GI property.
Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG $(1,...
user76479
3
votes
1
answer
2k
views
Properties of bipartite graphs
For a connected bipartite graph $G$ are the two following properties equivalent:
1)Every minimal cycle in $G$ has length 4, that is every cycle of length strictly greater than 4 can be divided in ...
- 31
3
votes
1
answer
105
views
Generalizations of the Triangle Removal Lemma to smaller exponents
The Triangle Removal Lemma states:
For all $\epsilon > 0$, there is a $\delta > 0$ such that any graph on $n$ vertices with at most $\delta n^3$ triangles may be made triangle-free by ...
- 1,379
3
votes
1
answer
559
views
Variants of Szemeredi's regularity lemma
I've noticed that the name 'Szemeredi's regularity lemma' is used for several closely related yet different statements about graphs.
Specifically, I'm interested in the distinction between two of ...
- 987
3
votes
3
answers
226
views
Counting the orderings of outward-directed trees where the degree of each vertex is $2$
Let $T$ be a connected directed tree with the following properties:
The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it).
$T$ has a ...
3
votes
1
answer
304
views
Directed Hypercube Minimal Cuts
If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices $U,...
- 434
3
votes
1
answer
92
views
Minor ordering for finite graphs
Let $\mathcal{G}_{<\omega}$ be the set of graphs $G = (V,E)$ such that $V = \{0,\ldots,n\}$ for some $n \geq 0$ and $E \subseteq \mathcal{P}_2(V) = \{\{a,b\} : a,b \in V \textrm{ and } a\neq b\}$. ...
- 45.5k
3
votes
2
answers
436
views
Graph game minimum vertex degree
Consider the following graph game, given a graph $G=(V,E)$ on $n$ vertices with minimum degree $ \gg \log(n)$. Players are BR and MA (BR moves first):
BR claims an unclaimed edge from $E$, adds it to ...
- 75
3
votes
2
answers
397
views
Independent Sets in random geometric graphs
I was wondering if a lot is known about independent sets in Random Geometric graphs? Most google searches don't bring up much. In addition I'm interested in any algorithms used for finding independent ...
- 903
3
votes
1
answer
114
views
Hamiltonicity of random graphs with high girth
We say that $G\sim G_{n,f}$ (for $f=f(n)$) if $G$ is chosen uniformly at random from all graphs on $n$ vertices with girth $g(G)\ge f(n)$. Is there any threshold function $F(n)$ such that when $f\ll F$...
- 221
3
votes
1
answer
441
views
Cycles in directed graphs
Let G be a finite directed graph (allowing multiple edges). We define a cycle (as usual) to be a sequence of edges $e_0, e_1, \dots, e_{n-1}$ (up to cyclic permutation) such that the terminal vertex ...
- 4,669
3
votes
1
answer
841
views
Color identical pairs and the 4-color theorem
If one could prove that for every 4-chromatic planar graph $X$ every color identical pair in $X$ is separated by a cycle, would that be a proof of the 4-color theorem?
Explanation:
A pair of ...
3
votes
1
answer
144
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 ...
- 599
3
votes
1
answer
274
views
About an equivalent to Tutte's 5-flow Conjecture
A while back I remember reading that F. Jaeger proved that Tutte's $5$-flow conjecture is equivalent to a statement about the co-planarity of a certain set of points in some euclidean space. But I ...
- 1,034
3
votes
2
answers
433
views
Correspondence between spanning Trees and Even Subgraphs in a Graph
Let $G$ be a connected graph and $T$ a spanning tree of $G$. For $e \in E(G) - E(T)$, Let $C_{e}$ denote the unique cycle in $T + e$.
Let $H(T)$ be the the subgraph of $G$ induced by symmetric ...
- 1,034
3
votes
2
answers
244
views
Two graph constructions: new, old?
Let $G=(V,E)$ be a simple, undirected graph. Let $|V(G)|=n$ and $|E(G)|=m$.
We consider connected graphs only. We write $i\sim j$ if $i$ and $j$ form an
edge. Let $N(i)=\{j:i\sim j\}$. We write $d(i)=|...
user3409
3
votes
1
answer
324
views
Graphs with polynomial volume growth
Let $G = (V,E)$ a graph, equipped with graph distance (i.e. for $x,y \in V$, the distance $d(x,y)$ is the length of the minimum path connecting $x$ and $y$). For $x \in V$ and $r \in \mathbb N$, ...
- 399
3
votes
1
answer
199
views
On cycles in self-centered graphs
Let $G$ be (connected) self-centered graph, i.e. $r(G)=d(G)=m<\infty$.
My question is following
Does $G$ always contains $C_{2m}$ or $C_{2m+1}$ as a subgraph?
- 737
3
votes
1
answer
176
views
Primes and ihara zeta function on graphs
The ihara zeta function of a graph $X$ is defined as
$$\zeta_X(u)=\prod_{ [C] }(1-u^{v(C)})$$
where the product is over the primes of the graph( A.Terras Zeta functions of graphs a stroll through the ...
3
votes
2
answers
434
views
Geodesics in Graphs:Shortest Paths vs Going as Straight Ahead as Possible
According to Wikipedia http://en.wikipedia.org/wiki/Geodesic, a geodesic " is a generalization of the notion of a "straight line" to "curved spaces " and further " In the presence of an affine ...
- 12.7k
3
votes
1
answer
624
views
Strongly regular graphs with the same parameters as Paley graph
It is known that the Paley graph $P(q)$ for $q = 5, 9, 13$ or $17$ vertices are the only strongly regular graph with the parameters as $P(q)$.
If $q \geq 25$, is the following assertion true:
...
- 3,708
3
votes
1
answer
441
views
What is the expected value for this
If there are $8$ random points in the plane whose horizontal coordinate
and vertical coordinate are uniformly distributed on the open interval
$\left(0,1\right)$, what is the expected largest size of ...
- 31
3
votes
1
answer
148
views
Search for common substructures in list of graphs
I have had the following problem on several occasions and I was wondering whether there is a general technique to solve this problem.
Given a list of graphs with property $P$. Is there a general ...
- 563
3
votes
1
answer
211
views
Hypergraph coloring problem motivated by legal billards racks
Motivation
There are several rules about what makes a rack legal for a game of eight-ball: the top ball has to be a solid, the eight-ball is in the middle, the two bottom vertices have to be one ...
- 22.9k
3
votes
1
answer
372
views
The degrees in a random subgraph
Fix some positive integers $N$ and $d_k$, $k=1,2,\dots$ with $N=\sum_{k=1}^\infty d_k$.
Suppose you have a graph $G$ taken randomly uniformly among the set of all (unoriented) graphs with $N$ ...
3
votes
2
answers
170
views
Faithfully embeddable graphs
Consider a weighted graph $G$ with weights $\omega_{ii}=0$, $\omega_{ij}=\omega_{ji}>0$, obeying the triangle inequality. One might want to ask into which metric spaces $X$ such a graph can be ...
- 9,628