Lights Out

This column is devoted to mathematics for fun. What better purpose is there for mathematics? To appear here, a theorem or problem or remark does not need to be profound (but it is allowed to be); it may not be directed only at specialists; it must attract and fascinate. We welcome, encourage, and frequently publish contributions from readers—either new notes, or replies to past columns.     

Langton's turmite meets Lights Out

The solution to the game of Lights Out and its many variants have been well studied. This article introduces Langton's turmite to the game of Lights Out and discusses when Langton's turmite can solve Lights Out on a torus. The article also explores the behavior of multiple Langton's turmites on a Lights Out on a torus. © 2014 Wiley Periodicals, Inc. Complexity 21: 155–161, 2016     

How to Turn All Lights Out

---

How to Turn All Lights Out

---

     

A note on graphs spanned by Eulerian graphs

We show that the problem raised by Boesch, Suffel, and Tindell of determining whether or not a graph is spanned by an Eulerian subgraph is NP-complete. We also note that there does exist a good algorithm for determining if a graph is spanned by a subgraph having positive even degree at every node.     

Minesweeper on graphs

Minesweeper is a popular single player game. It has been shown that the Minesweeper consistency problem is NP-complete and the Minesweeper counting problem is #P-complete. In this paper, we present efficient algorithms for solving these problems for Minesweeper graphs with bounded treewidth. Our algorithms turn out to be much better than those based directly on dynamic programming. The algorithms mostly use of algebraic operations on multivariate polynomials, so that one may use existing software to implement them easily.     

Polynomials on graphs

Let G be a simple graph with adjacency matrix A, and p(x) a polynomial with rational coefficients. If p(A) is the adjacency matrix of a graph, we denote that graph by p(G). We consider the question: Given a graph G, which polynomials p(x) give rise to a graph p(G) and what are those graphs? We give a complete answer if G is a distance-regular graph. We then derive some general relations between the polynomials p(x), the spectrum of A, and the automorphism group of G.     

关于分数k-因子临界图与分数k-可扩图的若干结果

一个简单图G, 如果对于V(G)的任意k元子集S, 子图G-S都包含分数完美匹配, 那么称G为分数k-因子临界图. 如果图G的每个k-匹配M都包含在一个分数完美匹配中, 那么称图G为分数k-可扩图. 给出一个图是分数k-因子临界图和分数k-可扩图的充分条件, 并给出一个图是分数k-因子临界图的充分必要条件.     

The Normality of Cayley (Di)graphs of Out valency 3 of Dihedral Group of Order 4p

§１．ＩｎｔｒｏｄｕｃｔｉｏｎＬｅｔＧｂｅａｆｉｎｉｔｅｇｒｏｕｐａｎｄＳａｓｕｂｓｅｔｏｆＧｎｏｔｃｏｎｔａｉｎｉｎｇｔｈｅｉｄｅｎｔｉｔｙｅｌｅｍｅｎｔ１ｏｆＧ．ＷｅｄｅｆｉｎｅｔｈｅＣａｙｌｅｙ（ｄｉ）ｇｒａｐｈＸ＝Ｃａｙ（Ｇ,Ｓ）ｏｆＧｗｉｔ...     

R-domination on block graphs

The k-domination problem is to select a minimum cardinality vertex set D of a graph G such that every vertex of G is within distance k from some vertex of D. We consider a generalization of the k-domination problem, called the R-domination problem. A linear algorithm is presented that solves this problem for block graphs. Our algorithm is a generalization of Slater's algorithm [12], which is applicable for forest graphs.     

Quadratic forms on graphs

We introduce a new graph parameter, called the Grothendieck constant of a graph G=(V,E), which is defined as the least constant K such that for every A:E→ℝ,

Coordination games on graphs

We introduce natural strategic games on graphs, which capture the idea of coordination in a local setting. We study the existence of equilibria that are resilient to coalitional deviations of unbounded and bounded size (i.e., strong equilibria and k-equilibria respectively). We show that pure Nash equilibria and 2-equilibria exist, and give an example in which no 3-equilibrium exists. Moreover, we prove that strong equilibria exist for various special cases. We also study the price of anarchy (PoA) and price of stability (PoS) for these solution concepts. We show that the PoS for strong equilibria is 1 in almost all of the special cases for which we have proven strong equilibria to exist. The PoA for pure Nash equilbria turns out to be unbounded, even when we fix the graph on which the coordination game is to be played. For the PoA for k-equilibria, we show that the price of anarchy is between \(2(n-1)/(k-1) - 1\) and \(2(n-1)/(k-1)\). The latter upper bound is tight for \(k=n\) (i.e., strong equilibria). Finally, we consider the problems of computing strong equilibria and of determining whether a joint strategy is a k-equilibrium or strong equilibrium. We prove that, given a coordination game, a joint strategy s, and a number k as input, it is co-NP complete to determine whether s is a k-equilibrium. On the positive side, we give polynomial time algorithms to compute strong equilibria for various special cases.     

Subharmonic functions on graphs

We study the behaviour of subharmonic functions on a graph. We assume bounds on the growth of balls and functions in order to obtain Liouville type theorems.     

Progress on perfect graphs

 A graph is perfect if for every induced subgraph, the chromatic number is equal to the maximum size of a complete subgraph. The class of perfect graphs is important for several reasons. For instance, many problems of interest in practice but intractable in general can be solved efficiently when restricted to the class of perfect graphs. Also, the question of when a certain class of linear programs always have an integer solution can be answered in terms of perfection of an associated graph. In the first part of the paper we survey the main aspects of perfect graphs and their relevance. In the second part we outline our recent proof of the Strong Perfect Graph Conjecture of Berge from 1961, the following: a graph is perfect if and only if it has no induced subgraph isomorphic to an odd cycle of length at least five, or the complement of such an odd cycle. Received: December 19, 2002 / Accepted: April 29, 2003 Published online: May 28, 2003 Key words. Berge graph – perfect graph – skew partition Mathematics Subject Classification (1991): 05C17