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, ...

learn more… | top users | synonyms

5
votes
1answer
162 views

The number of connected components of a generalized hypecube

For $n$ and $m$ positive integers $n>m\ge 1$ define a graph as follows. The vertices are the binary strings of length $n$. Two vertices are adjacent if they differ in exactly $m$ consecutive bits. ...
2
votes
1answer
95 views

A 3-connected graph property by Tutte

Tutte (1961): A graph $G$ is $3$-connected if and only if there exists a sequence $G_0, ...,G_n$ of graphs that have the following two properties 1) $G_0 = K_4$ and $G_n = G$ 2) $G_{i+1}$ has an ...
3
votes
0answers
37 views

Balancing out edge multiplicites in a graph

Let $G$ be a multigraph with maximum edge multiplicity $t$ and minimum edge multiplicity $1$ (so that there is at least one 'ordinary' edge). Is there some simple graph $H$ such that the $t$-fold ...
7
votes
0answers
108 views

A published proof for: the number of labeled $i$-edge ($i \geq 1$) forests on $p^k$ vertices is divisible by $p^k$

Let $F(n;i)$ be the number of labeled $i$-edge forests on $n$ vertices (A138464 on the OEIS). The first few values of $F(n;i) \pmod n$ are listed below: $$\begin{array}{r|rrrrrrrrrrr} & i=0 ...
5
votes
2answers
211 views

Average number of distinguished leaves in a binary tree

By a binary tree, I mean in this question a full rooted binary tree in which left and right child are labeled. A leaf of such a tree is a vertex of degree at most 1 (most references would probably ...
3
votes
1answer
628 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 ...
2
votes
0answers
57 views

Smallest distribution of points with genuinely different clusterings

An hierarchical clustering algorithm for (finite) sets of points in a given metric space is essentially determined by its linkage criterion, which defines the distance between arbitrary (finite) sets ...
0
votes
0answers
79 views

The largest size of a boolean subgraph (a hypercube) of a given graph

Let $G(\mathbb{F}_2^n)$ denote the graph that represents the lattice of all subspaces of $\mathbb{F}_2^n$ (also called a Hasse diagram). I am interested in knowing if there exists a large hypercube ...
5
votes
2answers
197 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
1answer
98 views

genus of a finite simple undirected graph

Let $G$ be a finite simple undirected graph. Suppose there exist subgraphs $G_1,G_2,\dots,G_n$ of $G$, such that $G_i$ and $G_j$, have no common edges and have at most two common vertices, for each ...
3
votes
2answers
149 views

Is the domination number of a combinatorial design determined by the design parameters?

Let $D$ be a $(v,k,\lambda)$-design. By the domination number of $D$ I mean the domination number $\gamma(L(D))$ of the bipartite incidence graph of $D$. Is $\gamma(L(D))$ determined only by ...
5
votes
2answers
91 views

Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?

A tournament is an orientation of a complete graph. A feedback arc set is a set of arcs in a digraph whose removal leave the digraph acyclic. The feedback arc set problem consists in finding a ...
15
votes
1answer
563 views

Paul Erdős: Determine or estimate the number of maximal triangle-free graphs on n vertices

Among the collections of the open problems of Paul Erdős on the website of Professor Fan Chung, there is one called "number of triangle-free graphs". ...
4
votes
1answer
133 views

Nash Equilibrium in general graphical game

Any one has any ideas about how to compute the Nash Equilibrium in general graphical game? Especially, when the graph structure is not a tree.
5
votes
1answer
149 views

The proof of Belyi theorem by Lando and Zvonkin

I'm sorry for asking such a specific question, but i have trouble understanding one detail in the proof of Belyi's theorem in the book "Graphs on surfaces and their applications" by Lando and Zvonkin" ...
3
votes
1answer
132 views

Is the domination number NP for non-bipartite graphs?

Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?
2
votes
0answers
90 views

Proofs about Forbidden Minors

I am working on a problem which involves proving that a particular graph is a forbidden minor of the class of graphs that i am working on. Now i read kuratowskis theorem for planarity but i still ...
2
votes
1answer
171 views

Coloring vertices in a cubic lattice graph and counting edges between vertices of identical and vertices of distinct coloration

Take an $A \times B \times C$ cubic lattice graph $G$, and paint $k_1$ vertices with color $c_1$ & $k_2$ vertices with color $c_2$, where $(k_1 + k_2)$ is equal to the total vertex count. Let ...
4
votes
1answer
148 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 ...
5
votes
1answer
343 views

Flow of an integer

I've stumbled across this family of flow networks, and posted the sequence of maximal flows to OEIS: A238729. I can't find any reference to it either. Has anyone seen it? Here is the description: ...
8
votes
0answers
211 views

Connections between Riemann hypothesis for curves over finite fields and Ramanujan property for graphs

this question relates to the beautiful construction of expander graphs using Cayley graphs of $PGL_2(\mathbb{F}_q)$, as exposited by Davidoff-Sarnak-Valette in their book, Elementary Number Theory, ...
13
votes
1answer
633 views

Is every graph the center of some other graph?

The center of a graph $G$ is the set of vertices that minimize the largest distance to vertices in $G$, e.g., in the graph below, that radius is $4$:           Define the ...
12
votes
3answers
279 views

How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seems to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...
1
vote
1answer
103 views

Non-toroidality of a simple graph

Let $G$ be a simple undirected graph and $G_1$ and $G_2$ are two subgraphs of $G$, with $E(G_1) \cap E(G_2) =\emptyset$. Which of the following conditions would imply that $G$ is not toroidal: a; ...
3
votes
1answer
109 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 ...
3
votes
1answer
185 views

Calculating a generalized inverse (Moore–Penrose pseudoinverse)

I am considering a graph with $n$ edges with the following nicely structured adjacency matrix: \begin{equation} A_n= \begin{pmatrix} 0 & 0 & 0 &\cdots & 0 & 0 & 1\\ 0 & 0 ...
3
votes
0answers
70 views

When is an induced subgraph of a Johnson graph hamilton-connected?

The Johnson graph $J(n,k)$ has vertices which are the $k$-subsets of $\{1, 2, \dots, n\}$ where two vertices are adjacent iff their intersection has size $k-1$. A graph is hamilton-connected if every ...
4
votes
2answers
614 views

Do Random Walks on the Hexagonal Lattice have a limit?

For every positive integer $n$, consider a regular hexagon $\mathrm{H}_n$ such that the distance of each vertex from the center is $\frac{1}{\sqrt{n}}$. That in turn induces a tiling of ...
4
votes
0answers
141 views

Does the concept of connective constant make sense for any tiling of the plane?

First let me define what is the "connective constant" of a two dimensional lattice. Let $c_{n}$ denote the number of $n$ step self-avoiding walks starting from a fixed origin point in the lattice. ...
1
vote
4answers
269 views

Graphs with dangling edges

In conventional Graph Theory the role of Nodes and Edges is skewed: nodes are perfectly ok being aloof, but poor edges are always drawn between existing nodes (that is, the two maps from EDGES to ...
2
votes
2answers
126 views

Normal subgroups of automorphism group of infinite cubic tree

Let $T$ denote the unique (countably infinite) tree in which every vertex has degree $3$ and let $G=Aut(T)$ be the group of graph automorphisms of $T$. I'm interested in the properties of this ...
6
votes
1answer
160 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
1answer
182 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 ...
7
votes
1answer
403 views

Seeming contradiction about P vs NP between graphclasses.org and at least two papers about clique in even-hole-free graphs

I believe correctness about clique in even-hole-free graphs of graphclasses.org and the paper Vertex elimination orderings for hereditary graph classes, Pierre Aboulker, Pierre Charbit, Nicolas ...
4
votes
0answers
138 views

Genus of the graph $K_{m,2,2,2}$

What is the genus of this complete $4-$partite graph, $K_{m,2,2,2}$, where $m \in \mathbb{N}$? Thanks in advance.
0
votes
1answer
119 views

Which graph topology has the greatest eigenvalue?

I am looking at comparing multiple graph topologies based on their spectra. From the set of all $N\times N$ adjacency matrices, is there any result which points to the adjacency matrix with the ...
3
votes
1answer
593 views

Big binary tree as an induced subgraph

I believe this is true: Suppose $G$ is a graph. If $G$ has a subdivision of a large binary tree, prove that $G$ has an induced subgraph which is a subdivision of a large binary tree or the line ...
10
votes
2answers
178 views

Big Mono-Chromatic Subgraphs of Vertex 2-Colourings

I'm not a graph theorist, but the following quantity came up in my work and I'm curious if it has been studied. Given a connected finite graph $\Gamma = (V,E)$ define: $$ c(\Gamma) = \min_{f : V ...
1
vote
1answer
94 views

almost equitable partitions and spectra

If a graph $G$ has an equitable partition, then its charachteristic polynomial (for the adjacency matrix) has a divisor that can be seen as the characteristic polynomial (for the adjacency matrix) of ...
1
vote
1answer
110 views

How many edges can you put in a graph such that every edge belongs to a minimal $k$-cycle?

I am trying to solve: Given $n, k$, find maximum $m$ such that there exists a graph on $n$ nodes, $m$ edges such that every edge is part of a minimal $k$-cycle. I only care about the asymptotic ...
2
votes
1answer
130 views

Non-exchangeable unimodular graph

Let $G=(V,E)$ be an countably infinite, locally finite transitive graph. Say that $G$ is exchangeable if for every two vertices $v,w \in V$ there exists a graph homomorphism that maps $v$ to $w$ and ...
3
votes
1answer
124 views

Genus of a simple graph

Let $G$ is a finite simple undirected graph. Suppose there exist subgraph $G_1,G_2,\dots,G_n$ of $G$, such that $G_i \cong K_5$ or $K_{3,3}$, $E(G_i)\cap E(G_j) = \emptyset$ and $|V(G_i)\cap V(G_j)| ...
5
votes
3answers
260 views

How hard is it to determine if a weighted graph can be isometrically embedded in R^3?

Consider a graph $G$ with nonnegative edge weights. Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight? ...
0
votes
0answers
52 views

A particular method of removing edges from strong di-graphs

I have been mulling over a little puzzle I gave myself involving a particular type of iterative removal of edges from a digraph and I'm stuck -- thought I'd consult experts. Start with an ...
1
vote
0answers
30 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
0answers
161 views

vertex transitive and Cayley graphs

(all the graphs alluded to below are finite). Suppose I gave you a graph, and asked you whether it was vertex-transitive. How hard is that algorithmically? The second question is: suppose I gave you ...
4
votes
1answer
179 views

Reference request: “unoriented composition” in generalized categories

I'm looking for a generalized notion of category (really of symmetric multicategory) which, roughly speaking, doesn't make a distinction between sources and targets. Each "morphism" in such a category ...
8
votes
1answer
320 views

A combinatorial problem concerned with logic circuits

Consider a logic circuit with two-bit gates only. The length of each gate is the number of bit lines that the gate crosses. How hard is to compute the maximum length for a given circuit? Notice that ...
4
votes
1answer
364 views

Genus of a graph

Let $G$ is a simple undirected graph. Suppose $G$ has two subgraphs $G_1$ and $G_2$, such that $E(G_1)\cap E(G_2) =\emptyset$ ($E(G_i)$, stand for the set of edges of $G_i$). Then is it true that ...
3
votes
2answers
334 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 ...