# Tagged Questions

**3**

votes

**1**answer

74 views

### Extremal graph theory for directed graphs

In extremal graph theory, there are results such as
$$t(C_4,G)\geq t(K_2,G)^4,$$
where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and ...

**0**

votes

**1**answer

61 views

### Laplacian matrix of a graph with negative weights

I am trying to calculate the Laplacian and Adjacency matrix of a graphs for positive and negative weights. If a graph be simple with only non-negative weight it is easier. But in my graph I have some ...

**4**

votes

**1**answer

110 views

### Graph presentation of Lexicographic shifts

Consider a finite alphabet $\{0,1, \ldots, n-1\}$. Let $\Sigma_n = \mathop{\prod}\limits_{j=1}^{\infty}\{0, \ldots n-1\}$ be the set of infinite one sided sequences and $\prec$ the lexicographic ...

**1**

vote

**1**answer

73 views

### Neighborhood overlap matrix for a bipartite graph

Let $G$ be an undirected, simple, bipartite graph with parts $V$ (having $n$ vertices) and $W$ (having $m$ vertices). Define the following $n$-by-$n$ matrix: for any $i,j \in V$, $$a_{ij} = |N_i \cap ...

**1**

vote

**0**answers

47 views

### Can we make the weaker TPC tighter when we do the packing steiner trees?

The famous tree packing conjecture (TPC) posed by Gyarfas (see [1]) states:
$\textbf{Conjecture 1}$. Any set of $n − 1$ trees $T_n, T_{n−1}, . . . , T_2$ such that $T_i$ has $i$ vertices pack into ...

**5**

votes

**2**answers

171 views

### Genus of Tutte-Coxeter Graph

What is the genus of the Tutte-Coxeter graph -- the incidence graph of the
GQ of order 2? Seems like it should be well known, since nearly every other
parameter for that graph is known, but I can ...

**4**

votes

**1**answer

141 views

### Which hyperbolic tilings are Cayley graphs?

I realise the question is easy but after asking to a few people (and never getting a clear answer), I thought it could be instructive to ask it here:
Given a regular tiling of the hyperbolic plane is ...

**3**

votes

**1**answer

219 views

### Flow of an integer

I've stumbled across this family of flow networks, and posted the sequence of maximal flows to OEIS. It doesn't appear at this time. I can't find any reference to it either. Has anyone seen it?
...

**3**

votes

**1**answer

98 views

### The spectral radius of a modified graph

Let $H$ be a graph and let $G=H \vee K_{1}$ be obtained by creating a new vertex and joining it to every vertex in $H$.
This situation has many different names: $G$ is called the cone or the ...

**6**

votes

**1**answer

149 views

### What is/are the best bound/s on the sum of squares of degrees in a graph?

Let $G$ be a graph with degrees $d_{1},\ldots,d_{n}$. I am interested in upper bounds on
$$
\sum_{i=1}^{n}{d_{i}^{2}}.
$$
An example is de Caen's bound:
$$
\sum_{i=1}^{n}{d_{i}^{2}} \leq ...

**-2**

votes

**1**answer

177 views

### Natural constructions (not depending on parameters) [closed]

Consider graph clusterings as a prototypical example of (logical) constructions.
Let a clustering of a graph $(V,E)$ be any covering of $V$, i.e. a set $C$ with $\bigcup C = V$.
I am looking for a ...

**1**

vote

**0**answers

28 views

### Harmonic Bergman spaces on graphs

Harmonic Bergman spaces on Euclidean domains are a set of harmonic functions on a domain that are from $L^{p}$ of that domain. I tried to find something on harmonic Bergman spaces on graphs because we ...

**3**

votes

**2**answers

316 views

### A structure of the group of automorphisms of an infinite binary tree

My friend asked me to ask his question here. Where he can find (a paper or a book) containing a complete description (with the proof) of a structure of the group of automorphisms of an infinite binary ...

**4**

votes

**2**answers

203 views

### Cubic graphs decompositions

There are many interesting computational problems related to connected cubic graph decomposition. For instance, decomposition of cubic graph into a perfect matching and a connected 2-factor ...

**3**

votes

**1**answer

114 views

### Have chordal outerplanar graphs been studied before?

Recall a graph is chordal if it contains no induced cycle of length 4 or more, and outerplanar if it has a crossing-free embedding in the plane such that all vertices are on the same face. While ...

**6**

votes

**1**answer

130 views

### A family of skew-symmetric matrices corresponding to cycles in graphs

When investigating loops in Markov chains I ran into the following observation.
A cycle in a graph $G$ with $n$ vertices may be represented by a matrix $\Gamma \in \mathbb R^{n \times n}$ having the ...

**4**

votes

**1**answer

144 views

### Universal graphs on higher cardinals

The Rado graph contains every finite graph as induced subgraph, and its also holds for countable graphs. So it is an universal graph of size $\aleph_0$, which contains all graphs of size $\aleph_0$ as ...

**1**

vote

**1**answer

196 views

### Is this Graph parameter known?

Let $\lambda(G)$ denote the edge-connectivity of $G$.
Consider the following parameter:
$\rho(G) = \max_{X \subset V(G)} \min(\lambda(G[X]), \lambda(G[V(G) - X]))$
Has this parameter been studied? ...

**0**

votes

**0**answers

55 views

### Maximum Independent set of sparse graphs with few triangles

Notations used
$\alpha(G) = $ Max sized independent set of graph $G$.
$n(G) = $ Number of vertex in graph $G$.
Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being ...

**1**

vote

**0**answers

41 views

### complexity of in-dominating set

Is the decision problem In-Dominating Set NP-complete for digraphs of regular out-degree (greater than (n-2)/4, in particular)? I'm mainly looking for the reference.
Thanks for any answer!

**2**

votes

**2**answers

125 views

### Name for Kneser/Johnson-like graphs?

I wonder if the following simple generalization of Johnson and Kneser
graphs has a name? Let the vertex set of the graph $G(n,k,t)$ be the
set of $k$-element subsets of an $n$-set, with two $k$-sets ...

**3**

votes

**1**answer

382 views

### Is there a graph-theoretical proof of Tutte's theorem on matroids?

First of all, I'm not a mathematician and I hope this question isn't too elementary, but I got no answers on math.SE, and since this is a reference request on a relatively advanced theorem, I thought ...

**1**

vote

**0**answers

100 views

### Is the automorphism group of a homogeneous (locally finite) tree unimodular?

I have seen somewhere (that I don't remember now) that the (full) automorphism group of a k-regular tree is unimodular. I assume a k-regular tree is the same thing as the homogeneous tree of degree k ...

**11**

votes

**7**answers

420 views

### Does the notion of graphs with vertex multiplicity exist?

I need to use graphs where each vertex gets a natural number, $b(v)$, its multiplicity. These numbers indicate how many 'replications' of the vertex we have.
It is actually a way to write in a ...

**3**

votes

**2**answers

171 views

### Methods to approximate the betweenness centrality on large networks

To calculate the between centrality wiki def:
$g(v) = \sum_{s\neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$
of a node in a graph/network;$\sigma_{st}$ is the ...

**2**

votes

**0**answers

86 views

### Groups acting on non-locally-finite trees with independence and specified local actions

Suppose I have a biregular tree $T_{m, n}$ (not necessarily locally finite), with distinct cardinal numbers $m, n$, so Aut$(T_{m, n})$ acts on $T_{m, n}$ without inversion. Let $V_m$ be those vertices ...

**7**

votes

**1**answer

285 views

### Chromatic number of induced subgraphs as upper bound to the chromatic number

Motivation: At the Erdős100 conference in Budapest András Gyárfás presented some interesting conjectures. One of them was the following:
Given that in a graph $G$, every subgraph $H$ formed by ...

**2**

votes

**3**answers

135 views

### Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs

From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...

**3**

votes

**1**answer

101 views

### For what classes of comparability graphs are their complements also comparability graphs?

An interval graph is an intersection graph of real intervals, that is, an undirected graph whose vertices can be labeled with real intervals so that there is an edge between two vertices iff their ...

**5**

votes

**1**answer

265 views

### Random path in a graph

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given ...

**6**

votes

**2**answers

179 views

### Recovering a Weighted Graph from Shortest Path Distances

I am interested in the following problem (A) and its related formulation (B).
(A) Suppose that $G = (V,E,w)$ is an unknown weighted graph on the vertex set $V$ and that one has access to $d_G(v,v'), ...

**3**

votes

**2**answers

256 views

### Term for “Directed acyclic graph with exactly one sink and one source”

There's a theorem/lemma that states that a finite directed acyclic graph (DAG) has at least one sink and at least one source. Is there a term for a (finite) DAG with exactly one sink and one source?
...

**4**

votes

**1**answer

133 views

### Do right-profiles determine graphs up to isomorphism?

For graphs $G$ and $H$, let $h(G,H)$ denote the number of graph homomorphisms from $G$ to $H$.
Fix some enumeration $G_1,G_2,\ldots$ of (isomorphism classes of) the set $\mathbf{D}$ of finite graphs, ...

**5**

votes

**2**answers

234 views

### Fractional chromatic number, find reference to a particular alternate definition for

I'm searching for a reference to a particular alternate definition of the fractional chromatic number of graphs.
Let me review the most common definition and basic properties first.
Let $ G $ be ...

**-1**

votes

**1**answer

107 views

### Intersection graphs of 2-element subsets

I am interested in the intersection graphs of $\binom{X}{2}$, i.e. the set of all 2-element subsets of a (finite) set $X$.
[Motivation: One can represent every simple graph with $n$ vertices by an ...

**4**

votes

**0**answers

92 views

### Metrized categories

Motivation: Let $\Gamma = (V,E)$ be a directed graph. To each edge $e \in E$, choose a value $\kappa^e \in \mathbb R$, representing the cost of transporting one unit of "stuff" through the edge. Let ...

**2**

votes

**0**answers

181 views

### Incremental minimum spanning tree

Given a connected graph $G=(V,E)$ with a weight function $w:E\to\mathbb{R}$ and a subset $E_0\subseteq E$ such that the subgraph $(V,E_0)$ is connected, I am looking for a sequence $E_0\subseteq ...

**11**

votes

**0**answers

317 views

### Drawings of complete graphs with $Z(n)$ crossings

Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly
$$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor ...

**7**

votes

**2**answers

403 views

### Deriving Konig's Lemma directly from Infinite Ramsey's Theorem for triples

Let KL denote König's Lemma (for trees over $\mathbb{N}$), and RT(3) denote the
Infinite Ramsey Theorem for triples over $\mathbb{N}$ (notation as in Simpson's
book Subsystems of second order ...

**8**

votes

**3**answers

404 views

### How dense is the set of asymmetric graphs?

On $n$ nodes, we have $2^{n(n-1)/2}$ graphs. Asymmetric graph is a graph that has only trivial automorphism. We known that asymptotically almost all finite graphs are asymmetric. Therefore, in the ...

**2**

votes

**2**answers

284 views

### Is there any nontrivial monad on the category of graphs?

The question is in the title, but let me specify what I mean by the category of graphs.
In the context of this question, the category of graphs is the category of symmetric irreflexive relations. ...

**0**

votes

**0**answers

162 views

### counting k-cliques not also (k+1) on random graphs

consider the set of graphs with $n$ vertices and exactly half of all $\binom n 2$ possible edges.
looking for a formula that counts the number of these graphs that have a $k$-clique but not a ...

**12**

votes

**3**answers

456 views

### Estimate on currents in Cayley graphs

Take a Cayley graph $\Gamma$ (thought of as an electrical network with all edges having equal resistance) and break one edge $e$ and put a battery there. (Assume the graph has only one end* so that ...

**0**

votes

**1**answer

84 views

### complexity of dominating sets of regular graphs

Hi,
I believe it is just an easy question, but I have not found the answer: Is the optimization / decision problem DOMINATING SET NP-complete when restricted to regular graphs? Where can I find a ...

**7**

votes

**1**answer

241 views

### Which degree sequences are planar graphical?

The Erdős–Gallai theorem characterizes which degree sequences are graphical (i.e. realizable by a simple graph).
There has been some work on which degree sequences are planar graphical (i.e. ...

**4**

votes

**0**answers

286 views

### Tensor product of quivers

As a special case of a general construction I have constructed "accidentally" a tensor product of quivers aka directed multigraphs (aka directed graphs for category theorists). Probably this is ...

**3**

votes

**1**answer

389 views

### Combinatorial geodesics

[There has been a flaw in my definition - as Sergei and Andreas pointed out. I hope I could fix it.]
I want to understand how the concepts of directions, straight (or shortest) lines, and geodesics ...

**0**

votes

**2**answers

240 views

### Reference for “almost all graphs have diameter 2”

The property in the title is well-known. I am trying to find an original reference to its first appearance in print. The 4th edition of Graphs & Digraphs by Chartrand and Lesniak lists this as ...

**0**

votes

**1**answer

56 views

### Reduction of $f$-solubility to $1$-factor

This has been put in math.SE for a while without any responses.
Given $G$ and an $f:V(G)\to{\Bbb N}$, there exists a graph $G_f$ such that $G$ is $f$-soluble if and only if $G_f$ has a $1$-factor.
...

**2**

votes

**1**answer

89 views

### (Heuristic for) Partitioning n-partite weighted graphs into bounded n-cliques

Consider a complete $N$-partite graph $X$ with $X_n$ denoting the $n$-th vertex bin for $1 \leq n \leq N$, where we may assume that each $X_n$ has $k$ vertices for some universal constant $k$. Assume ...