Search

We introduce a pictorial notation for certain tensors arising in the study of association schemes, based on earlier ideas of Terwilliger, Neumaier and Jaeger. These tensors, which we call "scaffolds", obey a simple set of rules which generalize common linear-algebraic operations such as trace, matrix product and entrywise product. We first study an elementary set of "moves" on scaffolds and illustrate their use in combinatorics. Next we re-visit results of Dickie, Suzuki and Terwilliger. The main new results deal with the relationships among vector spaces of scaffolds with edge weights chosen from a fixed coherent algebra and various underlying diagrams. As one consequence, we provide simple descriptions of the Terwilliger algebras of triply regular and dually triply regular association schemes. We finish with a conjecture connecting the duality of Bose-Mesner algebras to the graph-theoretic duality of circular planar graphs. [ABSTRACT FROM AUTHOR]

Abstract: A nonidentity automorphism of a graph is said to be semiregular if all of its orbits are of the same length. Given a graph with a semiregular automorphism , the quotient of relative to is the multigraph whose vertices are the orbits of and two vertices are adjacent by an edge with multiplicity if every vertex of one orbit is adjacent to vertices of the other orbit. We say that is an expansion of . In [J.D. Horton, I.Z. Bouwer, Symmetric -graphs and -graphs, J. Combin. Theory Ser. B 53 (1991) 114–129], Horton and Bouwer considered a restricted sort of expansions (which we will call ‘strong’ in this paper) where every leaf of expands to a single cycle in . They determined all cubic arc-transitive strong expansions of simple (1, 3)-trees, that is, trees with all of their vertices having valency 1 or 3, thus extending the classical result of Frucht, Graver and Watkins (see [R. Frucht, J.E. Graver, M.E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971) 211–218]) about arc-transitive strong expansions of (also known as the generalized Petersen graphs). In this paper another step is taken further by considering the possible structure of cubic vertex-transitive expansions of general (1,3)-multitrees (where vertices with double edges are also allowed); thus the restriction on every leaf to be expanded to a single cycle is dropped. [Copyright &y& Elsevier]

Abstract: Golumbic, Kaplan, and Shamir [Graph sandwich problems, J. Algorithms 19 (1995) 449–473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown [C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete. [Copyright &y& Elsevier]

Abstract: The bandwidth of a graph G is the minimum of the quantity taken over all proper numberings f of G. The strong product of two graphs G and H, written as , is the graph with vertex set and with adjacent to if one of the following holds: (a) and are adjacent to and in G and H, respectively, (b) is adjacent to in G and , or (c) and is adjacent to in H. In this paper, we investigate the bandwidth of the strong product of two connected graphs. Let G be a connected graph. We denote the diameter of G by . Let d be a positive integer and let be two vertices of G. Let denote the set of vertices so that the distance between x and in G is at most d. We define as the minimum value of over all vertices x of G. Let denote the set of vertices z such that the distance between x and z in G is at most and z is adjacent to y. We denote the larger of and by . We define if G is complete and as the minimum of over all pair of vertices of G otherwise. Let G and H be two connected graphs. Among other results, we prove that if and , then . Moreover, we show that this result determines the bandwidth of the strong product of some classes of graphs. Furthermore, we study the bandwidth of the strong product of power of paths with complete bipartite graphs. [Copyright &y& Elsevier]

Abstract: In this paper, we provide an upper bound for the k-tuple domination number that generalises known upper bounds for the double and triple domination numbers. We prove that for any graph G,where is the k-tuple domination number; is the minimal degree; is the m-degree of G; if or 2 and if ; d is the average degree. [Copyright &y& Elsevier]

Abstract: We consider a generalization of the firefighter problem where the number of firefighters available per time step t is not a constant. We show that if the number of firefighters available is periodic in t and the average number per time period exceeds , then a fire starting at any finite number of vertices in the two dimensional infinite grid graph can always be contained. [Copyright &y& Elsevier]

Abstract: We prove that the acyclic chromatic index for all graphs with girth at least . We extend the same method to obtain a bound of with the girth requirement . We also obtain a relationship between and . [Copyright &y& Elsevier]

Abstract: Let be a finite non-empty graph, where V and E are the sets of vertices and edges of G, respectively, and and . A vertex magic total labeling is a bijection from to the consecutive integers with the property that for every , , for some constant h. Such a labeling is super if . MacDougall, Miller and Sugeng proposed the conjecture: If , , then has a super vertex-magic total labeling (VMTL). We prove that this conjecture holds true by means of giving a family of super VMTLs of , . [Copyright &y& Elsevier]

Abstract: Assume that is an undirected graph, and . For every , we denote by the set of all elements of C that are within distance one from . If all the sets for are non-empty, and pairwise different, then C is called a locating-dominating set. The smallest possible density of a locating-dominating set in the infinite triangular grid is shown to be . [Copyright &y& Elsevier]

Abstract: A graph X is said to be distance-balanced if for any edge of X, the number of vertices closer to u than to is equal to the number of vertices closer to than to u. A graph X is said to be strongly distance-balanced if for any edge of X and any integer k, the number of vertices at distance k from u and at distance from is equal to the number of vertices at distance from u and at distance k from . Exploring the connection between symmetry properties of graphs and the metric property of being (strongly) distance-balanced is the main theme of this article. That a vertex-transitive graph is necessarily strongly distance-balanced and thus also distance-balanced is an easy observation. With only a slight relaxation of the transitivity condition, the situation changes drastically: there are infinite families of semisymmetric graphs (that is, graphs which are edge-transitive, but not vertex-transitive) which are distance-balanced, but there are also infinite families of semisymmetric graphs which are not distance-balanced. Results on the distance-balanced property in product graphs prove helpful in obtaining these constructions. Finally, a complete classification of strongly distance-balanced graphs is given for the following infinite families of generalized Petersen graphs: , , , and . [Copyright &y& Elsevier]

Abstract: We study a robustness model for the minimum coloring problem, where any vertex of the input-graph has some presence probability . We show that, under this model, the original coloring problem gives rise to a new coloring version (called Probabilistic Min Coloring) where the objective becomes to determine a partition of into independent sets , that minimizes the quantity , where, for any independent set , . We show that Probabilistic Min Coloring is NP-hard and design a polynomial time approximation algorithm achieving non-trivial approximation ratio. We then focus ourselves on probabilistic coloring of bipartite graphs and show that the problem of determining the best k-coloring (called Probabilistic Min -Coloring) is NP-hard, for any . We finally study Probabilistic Min Coloring and Probabilistic Min -Coloring in a particular family of bipartite graphs that plays a crucial role in the proof of the NP-hardness result just mentioned, and in complements of bipartite graphs. [Copyright &y& Elsevier]

Abstract: The bondage number of a graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with a domination number greater than the domination number of G. In this paper, we show that the bondage number of the Cartesian product of two cycles and is equal to 4, i.e., for any . [Copyright &y& Elsevier]

Abstract: A framework is a straight line realization of a graph in , given by a map . We prove that if is an infinitesimally rigid framework then there is an infinitesimally rigid framework for which the points , , are distinct points of the grid, where . We also show that such a framework on G can be constructed in time. [Copyright &y& Elsevier]

Abstract: In this note, we characterize the minimally circular-imperfect graphs that have a major vertex. [Copyright &y& Elsevier]

Abstract: A graphic sequence is said to be potentially -graphic, if has a realization G containing , a clique of vertices, as a subgraph. In this paper, we give two simple sufficient conditions for a graphic sequence to be potentially -graphic. We also show that the two sufficient conditions imply a theorem due to Rao [An Erdös-Gallai type result on the clique number of a realization of a degree sequence unpublished.], a theorem due to Li et al [The Erdös–Jacobson–Lehel conjecture on potentially -graphic sequences is true, Sci. China Ser. A 41 (1998) 510–520.], the Erdös–Jacobson–Lehel conjecture on which was confirmed (see [Potentially -graphical degree sequences, in: Y. Alavi et al. (Eds.), Combinatorics, Graph Theory, and Algorithms, vol. 1, New Issues Press, Kalamazoo Michigan, 1999, pp. 451–460; The smallest degree sum that yields potentially -graphic sequences, J. Graph Theory 29 (1998) 63–72; An extremal problem on the potentially -graphic sequence, Discrete Math. 212 (2000) 223–231; The Erdös–Jacobson–Lehel conjecture on potentially -graphic sequences is true, Sci. China Ser. A 41 (1998) 510–520.]) and the Yin–Li–Mao conjecture on [An extremal problem on the potentially -graphic sequences, Ars Combin. 74 (2005) 151–159.], where is a graph obtained by deleting one edge from . [Copyright &y& Elsevier]

Abstract: In this extended abstract we state some definitions and results from our earlier paper [C.Paul and J.A.Telle. New tools and simpler algorithms for branchwidth. In European Symposium on Algorithm - ESA 2005. To appear in Lecture Notes in Computer Science, 2005. Full draft avalaible as LIRMM RR 05-017] and use these to characterize the class of edge-maximal graphs of branchwidth k. Similarly to the maximal graphs of treewidth k (the k-trees) they turn out to be a subclass of chordal graphs where every minimal separator has size k. [Copyright &y& Elsevier]

Abstract: In this version of the Cops and Robber game, the cops move in tandems, or pairs, such that they are at distance at most one after every move. We present a recognition theorem for tandem-win graphs, and a characterization of triangle-free tandem-win graphs. [Copyright &y& Elsevier]

Abstract: Let and be two integers. Suppose that G is a 2-edge-connected graph of order with minimum degree at least a. Then G has a 2-edge-connected -factor if every pair of non-adjacent vertices has degree sum at least . This lower bound is sharp. As a consequence, we have Ore-type conditions for the existence of a 2-edge-connected -factor in graphs. [Copyright &y& Elsevier]