Switching m-edge coloured graphs

Speaker: Gary MacGillivray, University of Victoria

Abstract:

An m-edge-coloured graph consists of a set of vertices, any two of which are either joined by an edge of one of m colours or not joined at all. The operation of switching at a vertex v of an m-edge-coloured graph with respect to an element of a subgroup \Gamma of S_m  permutes the colours of the edges incident with v.  Switching defines an equivalence relation on the set of all m-edge-coloured graphs;  G and H are \Gamma-switch-equivalent if there exists a sequence of switches that transform G into H.

We consider the following problems and their solutions.  For a fixed subgroup \Gamma of S_m:
1) determine the number of equivalence classes of k-vertex m-edge-coloured graphs under switching with respect to \Gamma.
2) how hard is it to determine whether given m-edge-coloured graphs G and H are \Gamma-switch equivalent?
3) for a fixed m-edge-coloured graph H, how hard is it to determine whether a given m-edge-coloured graph G can be switched with respect to \Gamma so that there is a homomorphism of the transformed m-edge-coloured graph to H?  (A homomorphism is a mapping of V(G) to V(H) that preserves edges and colours.)

We will also discuss extending these results to (m,n)-mixed graphs.  These have m different colours of edges and n different colours of arcs.

Zoom link:

https://us02web.zoom.us/j/86861499971?pwd=rTDAaju0TCu24asnaBGvkuNlT11KZ1.1

Meeting ID: 868 6149 9971

Passcode: 325258

« All Events

• This event has passed.

Atlantic Graph Theory Seminar

January 22, 2025 @ 3:30 pm - 4:30 pm

Ramsey numbers of signed graphs

Ben Seamone, Dawson College and Université de Montréal, Nathan Acheampong (Université de Montréal) Francis Clavette (Université de Montréal), Geˇna Hahn (Université de Montréal) Margaux Marseloo (Université Paris-Saclay), Viktor Paardekooper (Université de Montréal), and Ben Seamone* (Dawson College & Université de Montréal)

Abstract: A signed graph is a pair (G, σ) where G = (V,E) is a graph and σ : E(G) → {+, −} is a signature which assigns a sign to each edge of G. One well-studied operation on signed graphs is that of switching at a vertex v ∈ V (G), by which we mean that every edge incident to v has its sign changed. Two signed graphs are called equivalent if one can be obtained from the other by a sequence of vertex switches. We call a complete signed graph positive (negative) if every edge is positive (negative). We study the following Ramsey problem on signed graphs – for positive integers s and t, what is the smallest n such that every signed complete graph on n vertices has an equivalent signed complete graph containing either a negative Ks or positive Kt? This “signed Ramsey number” is denoted r±(s, t). We show how a variety of approaches lead to upper and lower bounds on r±(s, t), settle an open problem by establishing the exact value of r±(4, t) for every t, and determine the asymptotics of r±(5, t) and r±(6, t).

Zoom link:

https://us02web.zoom.us/j/86861499971?pwd=rTDAaju0TCu24asnaBGvkuNlT11KZ1.1

Meeting ID: 868 6149 9971

Passcode: 325258

Speakers: Prangya Parida, U. Ottawa, and Kiara McDonald, U. Victoria

Zoom link:  https://us02web.zoom.us/j/86415230827?pwd=QUxLUnlMdWYzL05zSUJ4bnBCOUJnZz09

Prangya Parida:

Title: Cover-free families on graphs

Abstract: A family of subsets of a t-set is called a d-cover-free family if no subset is contained in the union of any d other subsets. We denote by t(d, n) the minimum  t for which there exists a d-cover-free family of a t-set with n subsets. Cover-free families (CFF) have wide applications in combinatorial group testing, where a d-CFF(t, n) can be used to identify d defective items in a group of n items with t tests. It is well-known that t(1, n) can be obtained by applying the famous Sperner’s Theorem. For d \geq 2, we rely on bounds for t(d, n).  Erdös, Frankl, and Füredi provided bounds for t(2, n) using the probabilistic method, given by 3.106 \log(n) < t(2, n) < 5.512 \log(n). Using a derandomization technique, Porat and Rothschild presented a deterministic polynomial-time algorithm to construct d-CFFs that achieves t = O(d^2 \log(n)). Some upper bounds on t(2, n) (in some cases exact bounds) for small values of n are provided by Li, van Rees, and Wei in 2006.

   In this talk, we extend the definition of a cover-free family to include a graph G, which we denote as \overline{G}-CFF, where the edges of the graph specify the pair of subsets whose union must not cover any other subset. We denote by t(G)  the minimum t for which there exists a \overline{G}-CFF. The traditional 2-CFF(t, n) is a special case of \overline{G}-CFF when G  is a complete graph of n vertices. This generalization of cover-free families provides a richer combinatorial structure  that lies between being a 1-CFF and a 2-CFF.

   We will discuss some classical results on cover-free families, along with general constructions of \overline{G}-CFFs, as well as specific constructions for certain families of graphs. We prove that for a graph G with n vertices,  t(1, n) \leq t(G) \leq t(2, n) and show that for an infinite family of Star graphs S_n with n vertices, t(S_n) = t(1, n). Interestingly, we also give a construction of CFFs on a Path (P_n) or Cycle (C_n) with n vertices using a mixed-radix Gray code. This yields an upper bound for t(P_n) and t(C_n) that is smaller than the lower bound of t(2, n) mentioned above.

   This is joint work with Lucia Moura.

——————————————————

Kiara McDonald:

Title: Broadcast Independence in Trees

Abstract: In the area of Graph Theory, the well-known problems of domination, packing and independence are generalized by broadcast domination, broadcast packing and broadcast independence. As an analogy and application, consider a city, where one wants to place cell towers of different signal strengths subject to certain conditions. If every building in the city hears the signal from at least (respectively at most) one tower, then the broadcast is dominating (respectively  packing). If no tower hears the signal from another tower, the broadcast is independent. The sum of the tower signal strengths is called the cost of the broadcast. The total cost of a maximum independent broadcast is called the broadcast independence number.

Our research was focused on determining explicit formulas and polynomial time algorithms for the broadcast independence number of various types of graphs. This parameter is difficult to compute for graphs in general, so we restrict the problem to specific classes of graphs to make use of their special structural properties to solve the problem. For a graph from a given class, we constructed a new graph, called the broadcast ball intersection graph. We were able to show that if the broadcast ball intersection graph is weakly chordal, then broadcast independence is polynomial time solvable for the given class of graphs. In this talk, we will focus on the broadcast ball intersection graph of trees. This talk is based on joint work with Richard Brewster (TRU) and Jing Huang (UVic).