# Tagged Questions

59 views

### Reconstructing a function from its variants that negate one argument

Call two functions $g(x_1,\ldots,x_n)$ and $h(x_1,\ldots,x_n)$ from complex numbers to complex numbers equivalent if they are the same up to the order of their arguments. Formally: there is a ...
86 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 ...
62 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 ...
114 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 ...
74 views

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 ...
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 ...
317 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 ...
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 ...
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 ...
131 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 ...
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 ...
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? ...
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 ...
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!
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 ...
391 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 ...
101 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 ...
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 ...
172 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 ...
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 ...
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 ...
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 ...
103 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 ...
267 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 ...
180 views

318 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 ...
404 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 ...
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 ...
285 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. ...
168 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 ...
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 ...
85 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 ...
243 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. ...
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 ...
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 ...
### 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. ...