Motivated by problems involving triangle-decompositions of graphs, we examine the facet structure of the cone \( \tau_n \) of weighted graphs on \( n \) vertices generated by triangles. Our results include enumeration of facets for small \( n \), a construction producing facets of \( \tau_{n+1} \) from facets of \( \tau_n \), and an arithmetic condition on entries of the normal vectors. We also point out that a copy of \( \tau_n \) essentially appears via the perimeter inequalities at one vertex of the metric polytope.

We consider the problem of detecting an intruder in a network where there are two types of detecting devices available. One device can determine the distance from itself to the intruder and the other can see the vertex it occupies as well as all adjacent vertices. The problem is to determine how many devices are required and where they should be placed in order to determine a single intruder’s location. We show that on the one hand, finding the minimum number of devices required to do this is easy when the network is a tree with at most one leaf adjacent to any vertex, while on the other hand finding this number is an NP-complete problem even for trees with at most two leaves adjacent to any vertex.

We present a 2-edge-coloured analogue of the duality theorem for transitive tournaments and directed paths. Given a 2-edge-coloured path \( P \) whose edges alternate blue and red, we construct a 2-edge-coloured graph \( D \) so that for any 2-edge-coloured graph \( G \),

\[
P \to G \iff G \not\to D.
\]

The duals are simple to construct, in particular \(|V(D)| = |V(P)| -1.\)

An edge coloring \( c \) of a graph \( G \) is a royal \( k \)-edge coloring of \( G \) if the edges of \( G \) are assigned nonempty subsets of the set \( \{1,2,\dots,k\} \) in such a way that the vertex coloring obtained by assigning the union of the colors of the incident edges of each vertex is a proper vertex coloring. If the vertex coloring is vertex-distinguishing, then \( c \) is a strong royal \( k \)-edge coloring. The minimum positive integer \( k \) for which \( G \) has a strong royal \( k \)-edge coloring is the strong royal index of \( G \). It has been conjectured that if \( G \) is a connected graph of order \( n \geq 4 \) where \( 2^{k-1} \leq n \leq 2^k – 1 \) for a positive integer \( k \), then the strong royal index of \( G \) is either \( k \) or \( k+1 \). We discuss this conjecture along with other information concerning strong royal colorings of graphs. A sufficient condition for such a graph to have strong royal index \( k+1 \) is presented.

Let \( k \) be a positive integer, and \( G \) be a \( k \)-connected graph. An edge-coloured path is rainbow if all of its edges have distinct colours. The rainbow \( k \)-connection number of \( G \), denoted by \( rc_k(G) \), is the minimum number of colours in an edge-colouring of \( G \) such that, any two vertices are connected by \( k \) internally vertex-disjoint rainbow paths. The function \( rc_k(G) \) was introduced by Chartrand, Johns, McKeon, and Zhang in 2009, and has since attracted significant interest. Let \( t_k(n,r) \) denote the minimum number of edges in a \( k \)-connected graph \( G \) on \( n \) vertices with \( rc_k(G) \leq r \). Let \( s_k(n,r) \) denote the maximum number of edges in a \( k \)-connected graph \( G \) on \( n \) vertices with \( rc_k(G) \geq r \). The functions \( t_1(n,r) \) and \( s_1(n,r) \) have previously been studied by various authors. In this paper, we study the functions \( t_2(n,r) \) and \( s_2(n,r) \). We determine bounds for \( t_2(n,r) \) which imply that \( t_2(n,2) = (1 + o(1)) n \log_2 n \), and \( t_2(n,r) \) is linear in \( n \) for \( r \geq 3 \). We also provide some remarks about the function \( s_2(n,r) \).

A signed graph \( (G, \sigma) \) is a graph \( G \) together with a mapping \( \sigma \) which assigns to each edge of \( G \) a sign, either positive or negative. The sign of a closed walk in \( (G, \sigma) \) is the product of the signs of its edges (considering multiplicity). Considering signs of closed walks as one of the key structures of signed graphs, a homomorphism of a signed graph \( (G, \sigma) \) to a signed graph \( (H, \pi) \) is defined to be a mapping that maps vertices to vertices, edges to edges, and that preserves incidences, adjacencies, and signs of closed walks. This is a recently defined notion, closely related to sign-preserving homomorphisms of signed graphs (or, equivalently, to homomorphisms of 2-edge-colored graphs), that helps, in particular, to establish a stronger connection between the theories of coloring and homomorphisms of graphs and the minor theory of graphs.

When there exists a homomorphism of \( (G, \sigma) \) to \( (H, \pi) \), one may write \( (G, \sigma) \to (H, \pi) \), thus extending the graph homomorphism order to a partial order on the classes of homomorphically equivalent signed graphs. In this work, studying this order, we prove that this order forms a lattice. That is to say, for each pair \( (G_1, \sigma_1) \) and \( (G_2, \sigma_2) \) of signed graphs, representing their respective classes, both their join and meet exist. While proving this result, we also show the existence of categorical products for signed graphs.

The game of cops and robbers on a graph is a vertex pursuit game played by two players with perfect information. Per the rules of the game, a given graph is either inherently cop-win or robber-win. It is possible that adding any edge changes the inherent nature of a particular graph. Such a graph is maximal in the sense that no edge can be added without changing its “win-state”. Furthermore, if deleting any edge changes the “win-state”, then this graph is minimal. Join us as we walk this thin blue line between cop-win and robber-win and explore the good, the bad, and the ugly.

Let \( H \) be a hypergraph of order \( n_H = |V(H)| \) and size \( m_H = |E(H)| \). The transversal number \( \tau(H) \) of a hypergraph \( H \) is the minimum number of vertices that intersect every edge of \( H \). A linear hypergraph is one in which every two distinct edges intersect in at most one vertex. A \( k \)-uniform hypergraph has all edges of size \( k \). For \( k \geq 2 \), let \( \mathcal{L}_k \) denote the class of \( k \)-uniform linear hypergraphs. We consider the problem of determining the best possible constants \( q_k \) (which depends only on \( k \)) such that \( \tau(H) \leq q_k(n_H + m_H) \) for all \( H \in \mathcal{L}_k \). It is known that \( q_2 = \frac{1}{3} \) and \( q_3 = \frac{1}{4} \). In this paper we show that \( q_4 = \frac{1}{5} \), which is better than for non-linear hypergraphs. Using the affine plane \( AG(2,4) \) of order 4, we show there are a large number of densities of hypergraphs \( H \in \mathcal{L}_4 \) such that \( \tau(H) = \frac{1}{5} (n_H + m_H) \).

Let \( F \) be a (possibly improper) edge-coloring of a graph \( G \); a vertex coloring of \( G \) is adapted to \( F \) if no color appears at the same time on an edge and on its two endpoints. If for some integer \( k \), a graph \( G \) is such that given any list assignment \( L \) to the vertices of \( G \), with \( |L(v)| \geq k \) for all \( v \), and any edge-coloring \( F \) of \( G \), \( G \) admits a coloring \( c \) adapted to \( F \) where \( c(v) \in L(v) \) for all \( v \), then \( G \) is said to be adaptably k-choosable. A \((k,d)\)-list assignment for a graph \( G \) is a map that assigns to each vertex \( v \) a list \( L(v) \) of at least \( k \) colors such that \( |L(x) \cap L(y)| \leq d \) whenever \( x \) and \( y \) are adjacent. A graph is \((k,d)\)-choosable if for every \((k,d)\)-list assignment \( L \) there is an \( L \)-coloring of \( G \). It has been conjectured that planar graphs are \((3,1)\)-choosable. We give some progress on this conjecture by giving sufficient conditions for a planar graph to be adaptably 3-choosable. Since \((k,1)\)-choosability is a special case of adaptable \( k \)-choosability, this implies that a planar graph satisfying these conditions is \((3,1)\)-choosable.

A broadcast on a nontrivial connected graph \( G = (V,E) \) is a function \( f : V \to \{0,1,\dots,\operatorname{diam}(G)\} \) such that \( f(v) \leq e(v) \) (the eccentricity of \( v \)) for all \( v \in V \). The weight of \( f \) is \( \sigma(f) = \sum_{v \in V} f(v) \). A vertex \( u \) hears \( f \) from \( v \) if \( f(v) > 0 \) and \( d(u,v) \leq f(v) \). A broadcast \( f \) is independent, or hearing independent, if no vertex \( u \) with \( f(u) > 0 \) hears \( f \) from any other vertex \( v \). We define a different type of independent broadcast, namely a boundary independent broadcast, as a broadcast \( f \) such that, if a vertex \( w \) hears \( f \) from vertices \( v_1, \dots, v_k \), \( k \geq 2 \), then \( d(w,v_i) = f(v_i) \) for each \( i \). The maximum weights of a hearing independent broadcast and a boundary independent broadcast are the \textit{hearing independence broadcast number} \( \alpha_h(G) \) and the boundary independence broadcast number \( \alpha_{bn}(G) \), respectively.

We prove that \( \alpha_{bn}(G) = \alpha(G) \) (the independence number) for any 2-connected bipartite graph \( G \) and that \( \alpha_{bn}(G) \leq n – 1 \) for all graphs \( G \) of order \( n \), characterizing graphs for which equality holds. We compare \( \alpha_{bn} \) and \( \alpha_h \) and prove that although the difference \( \alpha_h – \alpha_{bn} \) can be arbitrary, the ratio is bounded, namely \( \alpha_h / \alpha_{bn} < 2 \), which is asymptotically best possible. We deduce that \( \alpha_h(G) \leq 2n – 5 \) for all connected graphs \( G \neq P_n \) of order \( n \), which improves an existing upper bound for \( \alpha_h(G) \) when \( \alpha(G) \geq n/2 \).