All Questions
Tagged with reference-request graph-theory
453 questions
1
vote
0
answers
54
views
Constructing graphs from subsets of a minimal alphabet
From an alphabet of $N$ letters, choose $n$ pairwise distinct subsets $ v_1,\dots,v_n$ of a fixed size $k$ and define a graph on $V=\{v_1,\dots,v_n\}$, which has an edge for each pair of vertices that ...
- 13.4k
3
votes
0
answers
55
views
Efficiently drawing graph of maximum degree $3$ with at most $o(n^2)$ crossings
Let $G$ be simple finite graph of order $n$ and maximum
degree $3$.
Can we efficiently draw $G$ with at most $o(n^2)$ crossings?
"Efficiently" means in time polynomial in $n$ or at worst
$\exp{o(n^2)...
- 25.4k
5
votes
1
answer
206
views
A simple requirement for a degree sequence to be graphical
The following theorem about the degree sequences of finite simple graphs is quite easy to prove from the Erdos-Gallai theorem.
Let $0 \lt \alpha \le \beta \lt n$ be integers. Call $(\alpha,\beta,n)...
- 37.7k
14
votes
4
answers
1k
views
Is the "Moebius Stairway" Graph Already Known?
It is a wellknown fact, that Moebius Ladder Graphs have $2n$ vertices, but nowhere could I find any hint of how to generalize them to Graphs with $2n+1$ vertices.
Last week I had the idea of giving up ...
- 13.2k
4
votes
2
answers
139
views
References studying properties of a graph which are stable under finite perturbation
Let's say two locally finite, connected, undirected, infinite graphs are "finite perturbations" of each other if one can remove a finite subset from each and obtain isomorphic graphs (which are now ...
- 4,304
0
votes
0
answers
97
views
Shortest hyperpath algorithm in intuitionistic fuzzy hypergraphs
I was looking for an algorithm to calculate the shortest hyperpath in intuitionistic fuzzy hypergraphs and I found only this article (which propose two algorithms).
Are there any others algorithms ...
- 101
5
votes
0
answers
308
views
Distance on Markov-chains/graphs and discrete Ricci-flow
I am trying to know if there is a notion of "distance" or pseudo-metric between markov-chains or graphs.
For the purpose of the question, the graph is weighted, and can be considered as labelled, so ...
- 51
6
votes
2
answers
936
views
Human brains considered as directed graphs
I assume that human brains can be considered as directed graphs with neurons as nodes and synapses as edges. I explicitly don't want to consider the weights, the dynamics of neural activity (based on ...
- 9,720
6
votes
0
answers
477
views
The topos of a graph
If $G$ is, for example, a finite directed graph, one can attach to it a topos $T_G$ whose objects are "$G$-sheaves". A $G$-sheave $F$ is the data of:
For each verticies $x$ a set $F(x)$, for each ...
- 42.4k
1
vote
1
answer
240
views
Maximum/minimum intersection of two graphs
I wonder if the following graph problems have been studied and have names.
Problem(s).
Given two $n$-vertex unlabeled graphs $G_1$ and $G_2$, find their maximum/minimum edge intersection. That is ...
- 655
5
votes
0
answers
158
views
Does this geometric graph have a name?
Along some geometrical speculations, I came across a graph $\Gamma$ defined as follows:
Let $S$ be the set of vertices of a regular $n$-gon. Then the "vertices" of
$\Gamma$ are the nonempty subsets ...
- 101
4
votes
3
answers
356
views
reference request: voltage in a resistor network is a unique harmonic function
An undirected graph may be regarded as a resistor network where each edge corresponds to a resistor of unit resistance. This paper covers such an approach.
On electric resistances for distance-...
- 419
5
votes
1
answer
310
views
A variant of Ramsey numbers
The well known Ramsey number $R(k)$ is the least integer $n$ so that every 2-edge coloring of $K_n$ contains a monochromatic $K_k.$
Another interpretation of the above definition is that every graph ...
- 3,463
8
votes
1
answer
488
views
Stephan Brandt's habilitation thesis
I am searching for a copy of Stephan Brandt's habilitation thesis, Dense graphs with bounded clique number. Brandt's thesis is from Freie Universität Berlin in 2001.
I've done what I can to track ...
- 462
10
votes
3
answers
490
views
How many colors do we need to avoid bichromatic triangles?
Ramsey theory studies whether a monochromatic subgraph (more generally, structure) appears when we color the edges of a complete graph with some colors.
I wonder if the following type of question has ...
- 18.9k
-1
votes
1
answer
191
views
Cordial Labeling of 4-regular graphs
My group is working on *Cordial Labeling of 4-regular graphs.
We were wondering if someone here knows whether this study has been done before.
If not, can someone help me how to know if the given 4-...
6
votes
0
answers
138
views
Counting $K_4$ on two graphs sharing the same vertices
Let $f(G)$ denote the number of $K_4$ in a graph $G$ and $e(G)$ denote the number of edges of $G$.
Consider two simple graphs $G_1$ and $G_2$ having the same set $V$ of $n$ vertices and let $H_1(U)$ ...
- 3,153
4
votes
0
answers
764
views
Counting loops in degree: 1 or 2?
Here's what seems to be an annoying technicality when dealing with loops in graphs.
In the literature on expander graphs (and surely not only), it seems to be the convention that a loop at vertex $v$ ...
- 997
7
votes
0
answers
232
views
The smallest order of a 4-chromatic graph of given girth
Let $n_4(g)$ denote the smallest order of a $4$-chromatic graph with girth $g$. It is known that $n_4(4)=11$ [2] and $n_4(5)=21$ [1]. By a famous proof of Erdös, it is known that $n_4(g)$ is well-...
- 537
2
votes
1
answer
255
views
Is the logic of directed graphs generated by a finite set of formulae?
We consider the logic of reflexive directed graphs, i.e. the set
${\bf L}_1$ of those propositional formulae $\varphi$ in the variables $p_i$, which are valid in exactly these graphs.
It is a proper ...
- 567
4
votes
0
answers
123
views
A color interpolation lemma
I need the following "color interpolation lemma". Actually I know a way to prove it, but I'm not very satisfied with that proof.
Lemma. Let $G=(V,E)$ be a (properly) colored graph with colors $1, \...
- 2,479
2
votes
0
answers
210
views
a continuous analogue of a graph theory question
I am reading a paper and it mentions a continuous analogue of a related graph theory question that people concern. The question is that suppose $E\subset Q=[0,1]^2$ has lebesgue measure $|E|>0$, is ...
- 21
0
votes
0
answers
77
views
Intersection Of Valentine Convex Sets
A set X is said to be m-convex , m integer >=2, if for each set of m points at least one of the associated line segments lies in X.
A 3-convex set is sometimes also known as Valentine convex after ...
- 313
0
votes
0
answers
307
views
Graph Coloring: Two adjacent vertices share same color
Consider, subgraphs $G_1, G_2,...... G_x$ of graph $G$. Each subgraph has $k$ vertices.
Now, Fix subgraph $G_1$ and consider another subgraph $G_k$ where $1 <k \le x$.
The edge set ...
- 267
1
vote
1
answer
298
views
maximal sets of vertices that avoids a clique
I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
- 11
4
votes
1
answer
4k
views
exact definition of Fiedler vector
For a given N-vertex similarity graph $ G=(V,A) $ the eigenvalues of the unrenormalized (graph) Laplacian may be denoted as
$$ 0= \mu_0 \leq \mu_1 \leq ... \leq \mu_N $$
where the corresponding ...
- 253
2
votes
1
answer
384
views
Graph Isomorphism for Triangle Free graph
Is there any specific computational complexity result of Graph Isomorphism for Triangle Free graphs?
Anything close to the subject will help and of course, I have searched Google.
- 267
2
votes
0
answers
115
views
Influence of independent variables on boolean functions?
Suppose a simple connected graph $G$ where its vertices are assumed to be independent. An event with uncertainty corresponds to each vertex. My instructor guides me that even though the vertices (...
- 143
3
votes
1
answer
510
views
Menger's Theorem for planar triangulations
I was reading the paper "Planar separators" by Alon, Seymour and Thomas (available on the first author's webpage). They consider a planar triangulation, that is, a maximally planar graph $G$ drawn in ...
- 1,169
5
votes
1
answer
423
views
The minimum number of Hamiltonian paths in a strongly connected tournament of order $n$
For $n\ge3$ let $a(n)$ be the minimum number of Hamiltonian paths in a strong (i.e., strongly connected) tournament of order $n.$
Where is $a(n)$ discussed in the literature? Is the exact value ...
- 13.4k
3
votes
0
answers
199
views
Is the class of Heyting algebras originating from directed graphs a variety?
The category RefGph of reflexive directed graphs
is the functor category $\hat{∆}_1=\mbox{Fun}(∆^◦_1,$Set), where $∆_1$ is
the simplex category truncated at level 1.
Hence the poset Sub(X) of ...
- 567
3
votes
1
answer
74
views
Generalizing series-parallel digraphs with feedback
There are common definitions of series-parallel (SP) graphs and digraphs: the basic idea is as follows. A SP graph (or digraph) has two distinguished vertices $s$ ("source") and $t$ ("target"). The ...
- 15.4k
0
votes
1
answer
115
views
Majority colorings
If $X$ is a non-empty set, we say that $M\subseteq X$ is a majority if $|M| > |X\setminus M|$.
Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ we set $N(v)=\{x\in V: \{x,v\} \in ...
- 48.9k
6
votes
2
answers
477
views
Heyting algebras originating from directed graphs
The category RefGph of reflexive directed graphs is the functor
category $\hat{∆}_1=\mbox{Fun}(∆^◦_1,$Set), where $∆_1$ is
the simplex category truncated at level 1.
Hence the poset Sub(X) of ...
- 567
5
votes
1
answer
274
views
Is there a polynomial-time algorithm to check if a signed graph contains an odd-K5 minor?
I suspect this exists, if anyone has a reference please that would be very helpful.
By signed graph, I mean each edge is designated either odd or even (e.g. as in Guenin's result for weakly bipartite ...
- 311
7
votes
0
answers
229
views
Has anyone seen these binary trees (Catalan-type related to the Gegenbauer polynomials and Motzkin paths)?
The OEIS entry A121448 enumerates binary trees with $n$ edges and $k$ vertices with outdegree 1.
Has anyone seen these trees?
The o.g.f. for this entry, $G(x,t)$, is essentially a discriminant ...
- 10.5k
1
vote
2
answers
122
views
Maximal Minimum Weight DAGs
In the case of undirected, connected graphs the name for the maximal cycle-free subgraph of minimal weight is called Minimum Spanning Tree, and the efficient algorithms for their calculation are well ...
- 13.2k
1
vote
0
answers
77
views
Non-adjacent Pair of Edges with Minimal Weight Sum
Given an weighted, undirected Graph $G(V,E)$ without loops or parallel edges,
what is the complexity of determining a pair of non-adjacent edges, whose sum of weights is w.l.o.g. minimal?
is that ...
- 13.2k
1
vote
0
answers
105
views
Primitivity of $AA^\top$
Let $A\in\mathbb{R}^{n\times n}$ be a non-negative and irreducible matrix. Consider $B:=AA^\top$. It can be proved (I can post a proof if needed) that the following condition is necessary and ...
- 2,712
32
votes
1
answer
2k
views
Should axiomatic set theory be translated into graph theory?
Recently I saw the abstract of a paper by Nash-Williams: ``Should axiomatic set theory be translated into graph theory?''. The abstract, taken from Mathscinet says the following:
The author ...
- 32.1k
8
votes
0
answers
435
views
Is there an "Erlangen Program" for Graph Theory?
There are certain graph theoretic problems (especially optimization problems), whose solution-subgraph (i.e. the set of vertices and edges)), is invariant under certain modifications (especially ...
- 13.2k
3
votes
0
answers
342
views
Finding many disjoint sub-trees with many leaves
Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...
- 419
6
votes
0
answers
116
views
Chromatic numbers for coloring-constrained graphs
I am interested in any and all articles about chromatic numbers applying to constrained colorings of a graph. For example, if a graph must be (properly) colored so that there is a 2-color path ...
- 91
3
votes
1
answer
606
views
Node-edge coloring of graphs
There must be work on this concept, but I am not finding it through
searches, perhaps using the wrong terminology.
Define a node-edge coloring of a graph $G=(V,E)$...
- 151k
3
votes
1
answer
107
views
Probabilistic many-to-one matching
Let $p<1$ be a constant. Consider two sets $A,B$ with $n$ and $nf(n)$ vertices, respectively, where $f(n)$ is an integer. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears ...
- 239
2
votes
2
answers
353
views
Matching with probabilistic edges
Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...
- 239
9
votes
1
answer
261
views
Expansion in strongly regular graphs
Have you seen the following statement proven anywhere?
Let $G$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$ with $\lambda,\mu>0$. Then there is no set $A$ of at least $n/4$ ...
- 93
4
votes
1
answer
339
views
Vertex-connectivity of connected, vertex-transitive graphs without $K_4$ is maximum possible
A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. Ann.,...
- 406
4
votes
0
answers
111
views
A relaxation of proper coloring
I am wondering if the following relaxation of proper coloring appears somewhere. I have tried some searching and have found a few relaxations of proper coloring, but none the coincides with what I ...
- 7,875
6
votes
3
answers
855
views
Fundamental solution of Discrete Laplace in the plane
We consider a discretization of the Laplace operator on $\mathbb Z^2$, https://en.wikipedia.org/wiki/Discrete_Laplace_operator
Then, it is natural to consider its fundamental solution $u$, i.e. $|u(x)...
- 5,063