Skip to main content
Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Code code:"if (foo != bar)"
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Saves in:saves
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with
Search options not deleted user 136218

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, topological-graph-theory, random-graphs, graph-colorings and several others.

2 votes
Accepted

Looking for a counterexample to a strengthening of the union-closed sets conjecture

A family of counterexamples was found at math.stackexchange using projective planes as I should have expected. I have copied the answer here for convenience: Let $n = q^2+q+1$ and consider a projecti …
Fabius Wiesner's user avatar
4 votes
1 answer
343 views

Looking for a counterexample to a strengthening of the union-closed sets conjecture

[Now crossposted at math.stackexchange] Let $\mathcal{F} = \{\{x_1, x_2\} : 1 \le x_1 \lt x_2 \le n \}$, $n \ge 8$, and let $\mathcal{G} = \{G_1, \ldots, G_n\}$ be a partition of $\mathcal{F}$ in $n$ …
Fabius Wiesner's user avatar
1 vote
2 answers
357 views

Lower bound for the size of a family of sets

Consider a family $\mathcal{G} = \{ A_1,B_1,\ldots,B_m \}$ of $m+1$ non-empty finite distinct sets with the following property: $$A_1 \cap B_k = \emptyset, 1 \le k \le m$$ Let $\mathcal{F} = \{A_1 \cu …
Fabius Wiesner's user avatar
4 votes
1 answer
155 views

Remove an edge from the Hasse diagram of a finite lattice

If we remove an edge from the Hasse diagram of a finite lattice, as long as any vertex maintain at least one upward edge and at least one downward edge, do we still always have a lattice from the resu …
Fabius Wiesner's user avatar
3 votes
2 answers
331 views

Algorithm to evaluate "connectedness" of a binary matrix

I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix: 111000011100001101000001001111111111000 111000011100001101000000101111111111000 1111 …
Fabius Wiesner's user avatar
1 vote
1 answer
73 views

Lower bound for the sum of the number of vertices of some subgraphs of a directed graph

Let $G$ be any simple weakly connected directed graph with vertices $V$, $\vert V \vert = n$. Let $V_1, \ldots, V_m$, $m = \binom{n}{k}$ be all subsets of $V$ of size $k$. Let $C(V_i)$ be the union of …
Fabius Wiesner's user avatar
1 vote
1 answer
106 views

Non-isomorphic walk-regular graphs with the same number of closed walks at any length

Are there known examples of couples of non-isomorphic walk-regular graphs with adjacency matrix $A_1$ and $A_2$ and such that $(A_1^k)_{i,i} = (A_2^k)_{i,i}$ for all $k \gt 0$?
Fabius Wiesner's user avatar
0 votes
1 answer
159 views

Isomorphism of two regular hypergraphs

Consider two undirected $k$-regular hypergraphs on $n$ vertices with (see e.g. OEIS A319190). Are the two hypergraphs isomorphic if an only if the two multisets of the sizes of their respective hypere …
Fabius Wiesner's user avatar
1 vote
0 answers
63 views

Lower bound for the minimum of the maximum frequency of an element - with restrictions

Consider a family $\mathcal{F}$ of non-empty sets, with $n=|\mathcal{F}|$ sets, $q=\left|\cup\mathcal{F}\right|$ elements in the universe, and $q\le n/4$. It is known that of the $\binom{n}{2}$ ways t …
Fabius Wiesner's user avatar
1 vote
1 answer
80 views

Improving a lower bound for the minimum of the maximum frequency of an element in a family o...

[Originally posted at math.stackexchange without answer] Consider a family $\mathcal{F}$ of $n=|\mathcal{F}|$ sets, $\emptyset \not\in \mathcal{F}$ and an universe $U(\mathcal{F})$ of $q=|U(\mathcal{F …
Fabius Wiesner's user avatar
1 vote
1 answer
241 views

Graphs with $n$ vertices and $m$ edges and more probable property

Following to my previous question on the same topic, I would like to have some opinions whether the present refinement have some chances to work or is doomed to fail. Given the positive integers $n$ a …
Fabius Wiesner's user avatar
1 vote
2 answers
222 views

Do all graphs with $n$ vertices and $m$ edges have a special property?

Given the positive integers $n$ and $m$, consider the set of graphs $\mathcal{G} = \{G=(V,E): |V|=n \land |E|=m\}$. For which values of $n$ and $m$ does the following requirement hold: $\forall G \in …
Fabius Wiesner's user avatar
0 votes
1 answer
97 views

Name and/or class of a graph?

Does the following graph: (with graph6 string FFzvO) have a name or belong to a special class? The DIMACS (bliss) format of it is: p edge 7 14 e 1 4 e 1 5 e 1 6 e 1 7 e 2 4 e 2 5 e 2 6 e 2 7 e 3 4 e …
Fabius Wiesner's user avatar
1 vote
0 answers
157 views

Given a graph, how to build another "difficult" isomorphic graph from it?

Suppose I want to test an algorithm for graph isomorphism check. Starting from a given graph, I would do a random permutation of vertices to build the second graph. Is there a way of making another is …
Fabius Wiesner's user avatar
1 vote
0 answers
83 views

Literature about graph isomorphism and incidence matrix [closed]

I would like to read some paper, if any, for some classes of graphs, regarding inverting (right/left inverting) the incidence matrix to solve the graph isomorphism problem. Or anyway some known facts …
Fabius Wiesner's user avatar