{'fraction_non_alphanumeric': 0.06521260189469046, 'fraction_numerical': 0.007931262392597489, 'mean_word_length': 3.7539267015706805, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A generalisation of Seymour's second neighbourhood conjecture

In this note we propose a generalisation of Seymour's Second Neighbourhood Conjecture to two directed graphs on a vertex set. We prove that this generalisation holds in the case of tournaments, and we show that a natural strengthening of this conjecture does not hold.


Introduction
In this note, all graphs are finite. Directed graphs (or digraphs) do not contain parallel edges, but may contain self-loops. Oriented graphs are directed graphs with no self-loops and directed 2-cycles. A digraph G on a vertex set V = V (G) can be represented by its set of edges, E(G), a subset of V × V . The first neighbourhood or out-neighbourhood of a vertex v in G is the We omit the subscripts G if the context is clear. In 1990, Seymour conjectured the following statement: Conjecture 1 (Seymour, see [1]). Every oriented graph has a vertex v satisfying d G is said to satisfy the second neighbourhood conjecture (SNC) if it has a vertex satisfying SNP.
In 1996, Fisher [2] proved the conjecture for tournaments, i.e. oriented graphs with an edge between every pair of vertices.
It will be convenient to consider also a weighted version of SNC. Suppose G is weighted by a non-negative real-valued function ω : V (G) → R ≥0 . The weight of a set of vertices is the sum of the weights of its members. We say that a vertex v of G satisfies the weighted second neighbourhood property (WSNP) if ω(N ++ (v)) ≥ ω(N + (v)). We say G satisfies the weighted second neighbourhood conjecture (WSNC) if for every such function ω, there is a vertex v satisfying WSNP.

Every oriented graph satisfies the weighted second neighbourhood conjecture.
Proof. Clearly (2) implies (1). Supposing (1), we first show WSNC holds for positive integer weights ω : V (G) → N, hence holds for positive rational weights. By continuity, WSNC holds for all non-negative real weights.
Given a weight ω : ) is an edge of G, over all possible i, j. We call this process blowing up vertex v with weight ω(v). Then G having the WSNP is equivalent to G ′ having the SNP, hence G satisfies the WSNC.

A generalisation
We start with a generalisation which turns out to be false and give a counterexample with 36 vertices. Then we give a modification of the generalisation which we believe is true.
Let A, B be digraphs on the same vertex set V . Recall that a digraph can be viewed as a subset of V × V , so standard set operations can be performed on them.
i.e. the graph with all edges of A reversed. We define the product graph AB to be the subset The second neighbourhood conjecture can be reformulated in the following way: This leads to a natural generalisation: Let A, B be directed graphs on a vertex set V such that Similar to SNC, this has a weighted version ω(AB(v)) ≥ ω(A(v)) + ω(B(v)) − ω(v), which is equivalent to the unweighted one. However, the weighted version turns out to be false. We provide 2 counterexamples, both with A, B having no 2-cycles.
Our first counterexample has A ⊂ B. We give the weights of each vertex and out-neighbours of A, B, AB in the This yields an unweighted counterexample with 64 vertices after blowing up. By replacing AB with AB ∪ BA, we obtain a weaker generalised conjecture:

Conjecture 3. Let A, B be directed graphs on a vertex set V such that
The weighted version is as follows: This generalises SNC by setting A = B. By replacing A, B with A ∩ B, A ∪ B, we may assume that A ⊂ B. The above counterexamples show that the union AB ∪ BA is required, even when A ⊂ B or B ⊂ A. The tournament version of the above conjecture holds; we give a proof based on the technique of winning and losing densities of Fisher [2]: Proof. We first assume that A ⊂ B. Set C = AB ∪ BA. Consider the oriented graph G with edges {(u, v) | u = v, (u, v) ∈ A}. By Theorem 1 of [2], G has a losing density. A losing density l is a weight function satisfying l(N + Thus we have l(N − Q (u)) ≥ l(N + Q (u)) for some u ∈ Q with l(u) > 0. For each w ∈ S 1 , we cannot have (w, u) ∈ B T , since otherwise we have Since l(u) > 0, l(N + G (u)) = l(N − G (u)). From l(N − Q (u)) ≥ l(N + Q (u)), we deduce that l(S 2 ) ≥ l(S 1 ). We want to show there is a v such that ω(C(v) \ B(v)) ≥ ω(A(v) \ {v}). In fact, we show stronger statement that But the sets C T (v) \ B T (v) and A T (v) \ {v} are just S 2 and S 1 defined above corresponding to v, and l(S 2 ) ≥ l(S 1 ), thus the above sum is non-negative.
We remark that, setting A = B, we recover the usual proof by Fisher [2] of the SNC for tournaments.