3
votes
1answer
75 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 ...
-1
votes
0answers
24 views

departure time/overlap algorithm [on hold]

i'm looking for "departure time/overlap algorithm" or any other idea. Suppose you have n trains and each one has a performance profile(how much electricity they need at the current time while driving ...
7
votes
4answers
278 views

Extremal examples for a folklore lemma on subgraphs of large minimum degree

It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by ...
1
vote
1answer
122 views

Degree Sequence Problem on $k$-Partite Graphs

The general Degree Sequence Problem asks for a simple undirected graph (that is a graph without self-loops and with no more than one edge between any pair of nodes) for which it holds that the degrees ...
3
votes
2answers
117 views

Definition of the Moebius Ladder Graph

I found two different definitions of the Moebius Ladder Graph, whose essential difference is, whether the smallest one shall be $K_4$ or $K_{3,3}$. according to Wikipedia ...
2
votes
2answers
111 views

Which graphs generate a matroidal independence complex?

The independence complex $I(G)$ of a graph $G=(V,E)$ has as point set the vertex set $V$ and as simplices the independent sets of $G$. Now, if $G$ is a well-covered graph (where all maximal ...
0
votes
0answers
39 views

Almost symmetric route in digraphs

Let $D=(V,E)$ be a digraph. A route of length $k$ in $D$ is a pair $L=(S,\sigma)$, where $S=(s_1,s_2,\dots,s_{k+1})$ is a sequence of $k+1$ elements of $V$, and ...
14
votes
1answer
1k views

What have simplicial complexes ever done for graph theory?

(I am asking in a somewhat tongue-in-cheek fashion, of course, but nevertheless...) Are there examples of results in "classical" [*] graph theory that have been achieved by using simplicial ...
1
vote
1answer
97 views

The edge chromatic number and pefectness of inflation of cubic graph

The inflation of graph $G$ is a graph $I(G)$ which is obtained by replacing each vertex $x$ by a complete graph $K_{\deg(x)}$ and joining each edge to a different vertex of $K_{\deg(x)}$. Let $G$ ...
4
votes
1answer
165 views

Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge. Note that the number of paths between two endpoints of a $k$-chain is $2^k.$ Question: Let ...
1
vote
0answers
102 views

Knight's metric: ellipse and parabola

Knight's metric is a metric on $\mathbb{Z}^2$ as the minimum number of moves a chess knight would take to travel from $x$ to $y\in\mathbb{Z}^2$. What does a parabola (or an ellipse) became with this ...
9
votes
3answers
697 views

Could a perfect squared square be split into two perfect squared squares?

This is a geometric puzzle though it might conceivably also define a special class of Pythagorean triples. A perfect squared square PSS is a square (as a plane figure) partitioned into smaller ...
1
vote
1answer
116 views

Max order for which connected Cayley Graphs are known to be Hamiltonian

There is a well-known conjecture that all connected Cayley graphs are Hamiltonian. For how large a value of n has the conjecture been verified (i.e., for all groups whose order is at most n)?
6
votes
1answer
142 views

Does high min degree and high odd girth imply near bipartiteness?

Say $G$ has odd girth at least $k$ and min degree $2n/k$. There is a classical result by Andrasfai, Erdos, and Sos that says that $G$ is bipartite. (Odd girth is the length of the shortest odd cycle ...
4
votes
4answers
308 views

Determine if a graph has a large clique

This question is quite specific and practical. I hope it is still relevant for MO and will not be removed. I have a collection $\mathcal{C}$ of graphs having from 5000-6000 vertices and edge density ...
5
votes
1answer
146 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
0answers
32 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 ...
5
votes
2answers
171 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 ...
0
votes
0answers
74 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 ...
3
votes
2answers
145 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 ...
2
votes
0answers
44 views

Any one know the results of tensor decomposition by hypergraph partitioning?

Tucker Decomposition and CANDECOMP/PARAFAC (CP) Decomposition are two widely used tensor decomposition methods. However, when we model the hypergraph into tensor, what's the connection between the ...
3
votes
1answer
112 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
1answer
108 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 ...
3
votes
1answer
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? ...
6
votes
1answer
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 ...
7
votes
1answer
392 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 ...
3
votes
1answer
581 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
171 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 ...
0
votes
0answers
48 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 ...
7
votes
1answer
303 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 ...
3
votes
2answers
186 views

Making a graph claw-free by adding as few edges as possible

Independent set is polynomial in claw-free graphs, so I am wondering if this can approximate independent set. By adding enough edges to $G$ and gets claw-free $G'$. IS in $G'$ is IS in $G$, so this ...
0
votes
0answers
102 views

What is the number of connected subgraphs with $n$ vertices of a labelled connected simple graph with $n$ vertices?

Suppose $G$ is a connected simple labeled graph. Let $n$, $e$, and $k$ be its number of vertices, edges, and the upper bound of the degree of a vertex, respectively. How many connected sub-graphs ...
6
votes
1answer
125 views

Hamiltonicity criteria for sparse graphs

Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course). There are three main classes of criteria for Hamiltonicity that I am aware of: ...
1
vote
0answers
46 views

Perfect Matchings in Biclique Decompositions of Multigraphs

Suppose you have the $K_{2n}$ covered by a multigraph consisting of $2n-1$ bicliques, each consisting of a partition of the vertex set into two sets of equal size. Here is a picture of $K_{6}$ with 5 ...
3
votes
1answer
50 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 ...
4
votes
2answers
136 views

class 1 vs class 2 in regular graphs

Vizing's theorem states that a graph can be edge-colored in either $\Delta$ or $\Delta+1$ colors, where $\Delta$ is the maximum degree of the graph. A graph with edge chromatic number equal to ...
2
votes
3answers
204 views

Regular graphs whose neighbourhoods induce matchings

Studying some problem I've arrived to the following notion. Let a $2r$-regular graph $G$ be called neighbour-matching if $N(v) = rK_2.$ In other words, the neighbourhood of any vertex induces a ...
1
vote
1answer
116 views

Upper-bound for maximal-cliques on perfect graphs

It has been proved by Moon and Moser in 1965 that any finite simple graph has at most $3^{|V|/3}$ maximal cliques. Still, some hereditary classes of graphs have very few maximal cliques in comparison ...
0
votes
0answers
65 views

Existence of a sequence of (almost) Moore irregular graphs embedded on closed surfaces

Let $S_{g}$ denote the genus $g$ closed orientable surface. I'm interested in disproving the existence of a certain configuration of simple closed curves on $S_{g}$. I'd be happy to go into more ...
3
votes
1answer
169 views

Equivalence of Hadamard Graph and Hadamard Matrix

I'm reading Distance Regular Graphs by Brouwer, Cohen, and Neumaier. In section 1.8, they explained Hadamard graphs. Conversion from a Hadamard Matrix into a Hadamard Graph An $n$-Hadamard graph $G$ ...
1
vote
1answer
171 views

Counting edges in embeddable CW-complexes in R^3

Using Euler's formula ($V-E+F = 2$ where $V$, $E$ and $F$ are the number of vertices, edges and faces), we can easily count the number of edges in maximal graphs that are embeddable in plane: 3n-6. I ...
15
votes
0answers
206 views

Is the Poset of Graphs Automorphism-free?

For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$. ...
3
votes
0answers
70 views

What is this expander-mixing-type graph property?

Fix $C>0$. I am interested in graphs with the following mixing property: $$\Big|E(S,T)-\frac{1}{2}|S||T|\Big|\leq C\sqrt{|S||T|\max\{|S|,|T|\}}$$ for every disjoint $S,T\subseteq V$. Note that ...
2
votes
1answer
143 views

Regular graphs with $a$ and $b$ Hamiltonian edges

Special case of this question. Let $G$ be $r$-regular Hamiltonian graph. An $a$ edge is an edge which is on every Hamiltonian cycle. A $b$ edge is an edge which is on no Hamiltonian cycle. $a(G)$ ...
5
votes
1answer
215 views

Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$. Consider the bipartite ...
7
votes
2answers
289 views

Graphs with many edges avoided by Hamiltonian cycles

Let $G$ be a $3$-connected Hamiltonian graph with at least one edge that belongs to each H-cycle of $G$. Some authors (e.g. in the link given here) call such an edge an a-edge and an edge that belongs ...
4
votes
2answers
177 views

Number of unlabelled planar graphs

What are the best known bounds on the number of non-isomorphic (unlabelled) planar graphs on $n$ vertices? Is there a simple proof that this number is at most exponential in $n$?
1
vote
1answer
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? ...
5
votes
0answers
106 views

Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph

According to a conjecture: Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common. Equivalent statement here Main question: ...
2
votes
1answer
146 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 ...