All Questions
11 questions
8
votes
0
answers
2k
views
What is the best lower bound for the domination number in regular graphs of girth 5?
The following theorem is a classical result (see [Alon and Spencer, The probabilistic method, 2nd ed., Theorem 1.2.2]):
Theorem: Let $G$ be a graph on $n$ vertices with minimum degree $d$. Then $G$ ...
- 161
7
votes
2
answers
560
views
What is a hypergraph minor?
Is there a theory of hypergraph minors? I could only find some attempts to define them at papers/theses, whose main topic was something else. What would be a useful definition? Does the hypergraph ...
- 19k
7
votes
0
answers
97
views
What is known about chromatic polynomial of hypergraph at $-1$
Let $H$ be a hypergraph and let $P_H$ denote its chromatic polynomial. I am interested in the best results interpreting $P_H(-1)$. I am interested both in the general case (which I think is hard) as ...
- 7,875
5
votes
1
answer
372
views
Graphs with minimum degree $\delta(G)\lt\aleph_0$
Let $G=(V,E)$ be a graph with minimum degree $\delta(G)=n\lt\aleph_0$. Does $G$ necessarily have a spanning subgraph $G'=(V,E')$ which also has minimum degree $\delta(G')=n$ and is minimal with that ...
- 13.4k
2
votes
0
answers
50
views
An equation involving fractional covering number of hypergraphs
Let $\mathcal{H}=(S,\mathcal{X})$ be a hypergraph, where $S = \{ s_1, \ldots, s_n \}$, and $\mathcal{X} = \{ X_1, \ldots, X_m \}$.
The dual hypergraph $\mathcal{H}^*$ of $\mathcal{H}$ is the ...
- 655
1
vote
2
answers
130
views
Constants for diagonal hypergraph Ramsey Theorem
For integers $n,s$, we write $K_n^{(s)}$ to denote the complete $s$-uniform hypergraph on $n$ vertices.
Given integers $k,s,r$, let $R(K_k^{(s)};r)$ denote the smallest $N$ such that, for every $r$-...
- 3,499
1
vote
0
answers
315
views
Definition of k-partite hypergraph
I would like to know the standard definition of k-partite hypergraph.
There are two natural generalizations of k-partite graph to k-partite hypergraph:
1. For all edges e, any two vertices in e are ...
0
votes
2
answers
331
views
Hypergraph cartesian join operation (over same vertex set)
Consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new ...
- 529
0
votes
1
answer
62
views
Standard names of two finitary properties of hypergraphs?
Now we are writing a paper on minimal covers and minimal vertex-covers in hypergraphs and would like to know if there are any standard names for the following two (dual) properties of a hypergraph $(V,...
- 41.9k
0
votes
0
answers
97
views
Shortest hyperpath algorithm in intuitionistic fuzzy hypergraphs
I was looking for an algorithm to calculate the shortest hyperpath in intuitionistic fuzzy hypergraphs and I found only this article (which propose two algorithms).
Are there any others algorithms ...
- 101
0
votes
0
answers
71
views
products/factoring of two hypergraphs with same vertex set?
all the basic products for graphs have been extended to hypergraphs[1].
is there a concept of a product of hypergraphs with the same vertex set? has this been studied?
normally the hypergraph ...
- 529