Search

Canonical decompositions, such as the Gallai–Edmonds and Dulmage–Mendelsohn decompositions, are a series of structure theorems that form the foundation of matching theory. The classical Kotzig–Lovász decomposition is a canonical decomposition applicable to a special class of graphs with perfect matchings, called factor-connected graphs, and is famous for its contribution to the studies of perfect matching polytopes and lattices. Recently, this decomposition has been generalized for general graphs with perfect matchings; this generalized decomposition is called the general Kotzig–Lovász decomposition. In fact, this generalized decomposition can be presented as a component of a more composite canonical decomposition called the Basilica decomposition. As such, the general Kotzig–Lovász decomposition has contributed to the derivation of various new results in matching theory, such as an alternative proof of the tight cut lemma and a characterization of maximal barriers in general graphs. Joins in grafts, also known as T -joins in graphs, is a classical concept in combinatorics and is a generalization of perfect matchings in terms of parity. More precisely, minimum joins and grafts are generalizations of perfect matchings and graphs with perfect matchings, respectively. Under the analogy between matchings and joins, analogues of the canonical decompositions for grafts are expected to be strong and fundamental tools for studying joins. In this paper, we provide a generalization of the general Kotzig–Lovász decomposition for arbitrary grafts. Our result also contains Sebö's generalization of the classical Kotzig–Lovász decomposition for factor-connected grafts. From our results in this paper, a generalization of the Dulmage–Mendelsohn decomposition, which is originally a classical canonical decomposition for bipartite graphs, has been obtained for bipartite grafts. This paper is the first of a series of papers that establish a generalization of the Basilica decomposition for grafts. [ABSTRACT FROM AUTHOR]

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]

A graphical design is a proper subset of vertices of a graph on which many eigenfunctions of the Laplacian operator have mean value zero. In this paper, we show that extremal independent sets make extremal graphical designs, that is, a design on which the maximum possible number of eigenfunctions have mean value zero. We then provide examples of such graphs and sets, which arise naturally in extremal combinatorics. We also show that sets which realize the isoperimetric constant of a graph make extremal graphical designs, and provide examples for them as well. We investigate the behavior of graphical designs under the operation of weak graph product. In addition, we present a family of extremal graphical designs for the hypercube graph. [ABSTRACT FROM AUTHOR]

We conjecture that all connected graphs of order n have von Neumann entropy at least as great as the star K 1 , n − 1 and prove this for almost all graphs of order n . We show that connected graphs of order n have Rényi 2-entropy at least as great as K 1 , n − 1 and for α > 1 , K n maximizes Rényi α -entropy over graphs of order n . We show that adding an edge to a graph can lower its von Neumann entropy. [ABSTRACT FROM AUTHOR]

A code X is (⩾ k)-circular if every concatenation of words from X that admits, when read on a circle, more than one partition into words from X , must contain at least k + 1 words. In other words, the reading frame retrieval is guaranteed for any concatenation of up to k words from X. A code that is (⩾ k)-circular for all integers k is said to be circular. Any code is (⩾ 0)-circular and it turns out that a code of trinucleotides is circular as soon as it is (⩾ 4)-circular. A code is k -circular if it is (⩾ k)-circular and not (⩾ k + 1)-circular. Due to the explosive combinatorics of trinucleotide k -circular codes, we developed three classes of algorithms based on: (i) the smallest directed cycles (directed girth) in graphs; (ii) the eigenvalues of matrices; and (iii) the files that incrementally save partial results. These different approaches also allow us to verify the computational results obtained. We determine here the growth functions of trinucleotide k -circular codes, k varying between 0 and 4, in the general case and in various particular cases: minimum, minimal, maximum, self-complementary k -, (k , k , k) - and self-complementary (k , k , k) -circular. [ABSTRACT FROM AUTHOR]

We study the algebraic rank of a divisor on a graph, an invariant defined using divisors on algebraic curves dual to the graph. We prove it satisfies the Riemann–Roch formula, a specialization property, and the Clifford inequality. We prove that it is at most equal to the (usual) combinatorial rank, and that equality holds in many cases, though not in general. [ABSTRACT FROM AUTHOR]

Combinatorial maps are widely used in image representation and processing, and measuring distance or similarity between combinatorial maps is therefore an important issue in this field. The existed distance measures between combinatorial maps based on the largest common submap and the edit distance have high computational complexity, and are hard to be applied in real applications. This paper addresses the problem of inexact matching between labeled combinatorial maps, and aims to find a rapid algorithm for measuring distance between maps. We first define joint-tree of combinatorial maps and prove that it can be used to decide of isomorphism between combinatorial maps. Subsequently, a distance measure based on joint-trees and an approximate approach are proposed to compute the distance between combinatorial maps. Experimental results show that the proposed approach performs better in practice than the previous approach based on approximate map edit distance. [ABSTRACT FROM AUTHOR]

Abstract: In this note we present House of Graphs (http://hog.grinvin.org) which is a new database of graphs. The key principle is to have a searchable database and offer–next to complete lists of some graph classes–also a list of special graphs that have already turned out to be interesting and relevant in the study of graph theoretic problems or as counterexamples to conjectures. This list can be extended by users of the database. [Copyright &y& Elsevier]

Abstract: In this paper we introduce a new parameter for a graph called the minimum universal rank. This parameter is similar to the minimum rank of a graph. For a graph G the minimum universal rank of G is the minimum rank over all matrices of the form where A is the adjacency matrix of G, J is the all ones matrix and D is the matrix with the degrees of the vertices in the main diagonal, and are scalars. Bounds for general graphs based on known graph parameters are given, as is a formula for the minimum universal rank for regular graphs based on the multiplicity of the eigenvalues of A. The exact value of the minimum universal rank of some families of graphs are determined, including complete graphs, complete bipartite graph, paths and cycles. Bounds on the minimum universal rank of a graph obtained by deleting a single vertex are established. It is shown that the minimum universal rank is not monotone on induced subgraphs, but bounds based on certain induced subgraphs, including bounds on the union of two graphs, are given. [Copyright &y& Elsevier]

Abstract: The linear program dual variables for weighted matching and its generalization to -factors are shown to be the weights of certain subgraphs: duals are the weights of certain maximum matchings or -factors; duals are the weights of certain 2-factors or -factors. Similar interpretations have been given for the bipartite case of these problems, where only duals occur, but our variant is included here for completeness. In all cases the duals are canonical in a well-defined sense; duals are canonical for matching and more generally for -matchings (a special case of -factors) but for -factors their support can vary. As weights of combinatoric objects the duals are integral for given integral edge weights, and so they give new proofs that the linear programs for these problems are TDI. [Copyright &y& Elsevier]

Abstract: In the paper, we will present two sufficient conditions for a bipartite graph to be Hamiltonian and a graph to be traceable, respectively. [Copyright &y& Elsevier]

Abstract: Zero forcing (also called graph infection) on a simple, undirected graph is based on the color-change rule: if each vertex of is colored either white or black, and vertex is a black vertex with only one white neighbor , then change the color of to black. A minimum zero forcing set is a set of black vertices of minimum cardinality that can color the entire graph black using the color change rule. The propagation time of a zero forcing set of graph is the minimum number of steps that it takes to force all the vertices of black, starting with the vertices in black and performing independent forces simultaneously. The minimum and maximum propagation times of a graph are taken over all minimum zero forcing sets of the graph. It is shown that a connected graph of order at least two has more than one minimum zero forcing set realizing minimum propagation time. Graphs having extreme minimum propagation times , , and are characterized, and results regarding graphs having minimum propagation time 1 are established. It is shown that the diameter is an upper bound for maximum propagation time for a tree, but in general propagation time and diameter of a graph are not comparable. [Copyright &y& Elsevier]

Abstract: This paper presents a simple algorithm to generate all ordered trees with exactly vertices including exactly leaves. The best known algorithm generates such trees in time per tree, whereas our algorithm generates such trees in time per tree in the worst case. [Copyright &y& Elsevier]

Abstract: We present a new type of lower bound for the spectral radius of a graph in which m nodes are removed. As a corollary, Cioabă’s theorem , which states that the maximum normalized principal eigenvector component in any graph never exceeds (with equality for the star), appears as a special case of our more general result. [Copyright &y& Elsevier]

Abstract: Let be the second largest eigenvalue of a graph. Powers (1988) gave some upper bounds of for general graphs and bipartite graphs, respectively. Considering that these bounds are not always attainable for connected graphs, we present sharp upper bounds of for connected graphs and connected bipartite graphs in this paper. Moreover, the extremal graphs are completely characterized. [Copyright &y& Elsevier]

Abstract: The minimum rank of a graph has been an interesting and well studied parameter investigated by many researchers over the past decade or so. One of the many unresolved questions on this topic is the so-called graph complement conjecture, which grew out of a workshop in 2006. This conjecture asks for an upper bound on the sum of the minimum rank of a graph and the minimum rank of its complement, and may be classified as a Nordhaus–Gaddum type problem involving the graph parameter minimum rank. The conjectured bound is the order of the graph plus two. Other variants of the graph complement conjecture are introduced here for the minimum semidefinite rank and the Colin de Verdière type parameter . We show that if the -graph complement conjecture is true for two graphs then it is true for the join of these graphs. Related results for the graph complement conjecture (and the positive semidefinite version) for joins of graphs are also established. We also report on the use of recent results on partial k-trees to establish the graph complement conjecture for graphs of low minimum rank. [Copyright &y& Elsevier]

Abstract: The problem of finding the minimum rank over all symmetric matrices corresponding to a given graph has grown in interest recently. It is well known that the minimum rank of any graph is bounded above by the clique cover number, the minimum number of cliques needed to cover all edges of the graph. We generalize the idea of the clique cover number by defining the rank sum of a cover to be the sum of the minimum ranks of the graphs in the cover. Using this idea we obtain a combinatorial solution to the minimum rank problem for an outerplanar graph. As a consequence the minimum rank of an outerplanar graph is field independent and all outerplanar graphs have a universally optimal matrix. We also consider implications of the main result to the inverse inertia problem. [Copyright &y& Elsevier]

Abstract: Let G be a simple graph, and let the least eigenvalue of the signless Laplacian of the graph G. In this paper we focus on the relations between the least eigenvalue and some parameters reflecting the graph bipartiteness. We introduce two parameters: the vertex bipartiteness and the edge bipartiteness , and show thatWe also define another parameter involved with a cut set, and prove thatwhere is the maximum degree of the graph G. The above two inequalities are very similar in form to those given by Fiedler and Mohar, respectively, with respect to the algebraic connectivity of Laplacian of graphs, which is used to characterize the connectedness of graphs. [Copyright &y& Elsevier]

Abstract: We investigate how the least eigenvalue of the signless Laplacian of a graph changes by relocating a bipartite branch from one vertex to another vertex, and minimize the least eigenvalue of the signless Laplacian among the class of connected graphs with fixed order which contains a given non-bipartite graph as an induced subgraph. [Copyright &y& Elsevier]

Abstract: In this paper we deal with two aspects of the minimum rank of a simple undirected graph G on n vertices over a finite field with q elements, which is denoted by . In the first part of this paper we show that the average minimum rank of simple undirected labeled graphs on n vertices over is , were . In the second part of this paper we assume that G contains a clique on k-vertices. We show that if q is not a prime then for and . It is known that for , and . We show that for and each there exists a graph G such that . For , and we show that . [Copyright &y& Elsevier]

Abstract: Let be an arbitrary simple graph. Godsil and Gutman in 1978 and Yan et al. in 2005 established different expressions for the matching polynomial in terms of for some families of matrices . This paper improves their results and simplifies the computation of . [Copyright &y& Elsevier]

Abstract: Motivated by a fundamental geometrical object, the cut locus, we introduce and study a new combinatorial structure on graphs. [Copyright &y& Elsevier]

Abstract: Among the cacti with vertices and cycles we determine a unique cactus whose least eigenvalue is minimal. We also explore cacti with vertices and among them, we find a unique cactus whose least eigenvalue is minimal. [Copyright &y& Elsevier]

Abstract: Let G =(V, E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the signless Laplacian matrix of G is Q(G)= D(G)+ A(G). In [5], Cvetković et al. have given the following conjecture involving the second largest signless Laplacian eigenvalue () and the index () of graph G (see also Aouchiche and Hansen [1]):with equality if and only if G is the star for the lower bound, and if and only if G is the complete bipartite graph for the upper bound. In this paper we prove the lower bound and characterize the extremal graphs. [Copyright &y& Elsevier]

Abstract: In 1970s, Gutman introduced the concept of the energy for a simple graph , which is defined as the sum of the absolute values of the eigenvalues of . This graph invariant has attracted much attention, and many lower and upper bounds have been established for some classes of graphs among which bipartite graphs are of particular interest. But there are only a few graphs attaining the equalities of those bounds. We however obtain an exact estimate of the energy for almost all graphs by Wigner’s semi-circle law, which generalizes a result of Nikiforov. We further investigate the energy of random multipartite graphs by considering a generalization of Wigner matrix, and obtain some estimates of the energy for random multipartite graphs. [Copyright &y& Elsevier]

Abstract: Suppose that G is an undirected graph, and that H is a spanning subgraph of whose edges induce a subgraph on p vertices. We consider the expression , where denotes the algebraic connectivity. Specifically, we provide upper and lower bounds on in terms of p, and characterise the corresponding equality cases. We also discuss the density of the expression in the interval . A bound on is provided in a special case, and several examples are considered. [Copyright &y& Elsevier]

Abstract: Suppose that G is a connected graph of order n and girth . Let k be the multiplicity of an eigenvalue of G. Sharp upper bounds for k are when , and otherwise. The graphs attaining these bounds are described. [Copyright &y& Elsevier]

Abstract: For a given graph , a non-increasing sequence of nonnegative integers is said to be potentially -graphic if there exists a realization of containing as a subgraph. The split graph on vertices is denoted by . In this paper, we give a Rao-type characterization for to be potentially -graphic. A simplification of this characterization is also presented. [Copyright &y& Elsevier]

Abstract: If X is a geodesic metric space and , a geodesic triangle is the union of the three geodesics , and in . The space is -hyperbolic (in the Gromov sense) if any side of is contained in a -neighborhood of the union of the two other sides, for every geodesic triangle in . We denote by the sharp hyperbolicity constant of , i.e. . The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. The main aim of this paper is to obtain information about the hyperbolicity constant of the complement graph in terms of properties of the graph . In particular, we prove that if , then , and that the inequality is sharp. Furthermore, we find some Nordhaus–Gaddum type results on the hyperbolicity constant of a graph . [Copyright &y& Elsevier]

Abstract: Consider the following generalization of the sequential group testing problem for 2 defective items, which is suggested by Aigner (1988) in : Suppose a graph contains one defective edge . Find the endpoints of by testing whether a subset of vertices of cardinality at most 2 contains at least one of the endpoints of or not. What is then the minimum number of tests, which are needed in the worst case to identify ? In Gerzen (2009) , this problem was partially solved by deriving sharp lower and upper bounds for . In addition, it was proved that the determination of is an NP-complete problem. Among others, it was shown that the inequality holds for graphs with 2-complexity and the edge set . In the present paper, we study the class of graphs for which this inequality is sharp and characterize these graphs in several ways. We suppose that for those graphs the 2-complexity can be computed in polynomial time by means of this characterization. [Copyright &y& Elsevier]

Abstract: The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. For a connected graph and two nonadjacent vertices and in of , recall that is the supergraph formed from by adding an edge between vertices and . Denote the Harary index of and by and , respectively. We obtain lower and upper bounds on , and characterize the equality cases in those bounds. Finally, in this paper, we present some lower and upper bounds on the Harary index of graphs with different parameters, such as clique number and chromatic number, and characterize the extremal graphs at which the lower or upper bounds on the Harary index are attained. [Copyright &y& Elsevier]

Abstract: We introduce a new type of order of sets of vertices. Using this concept, we describe the structure and the relationship between chordal, interval, cocomparability, and asteriodal triple-free graphs. [Copyright &y& Elsevier]

Abstract: We determine the values of the acyclic chromatic index of a class of graphs referred to as -dimensional partial tori. These are graphs which can be expressed as the cartesian product of graphs each of which is an induced path or cycle. This class includes some known classes of graphs like -dimensional meshes, hypercubes, tori, etc. Our estimates are exact except when the graph is a product of a path and a number of odd cycles, in which case the estimates differ by an additive factor of at most 1. Our results are also constructive and provide an optimal (or almost optimal) acyclic edge colouring in polynomial time. [ABSTRACT FROM AUTHOR]

Abstract: It is known that planar graphs without cycles of length from 4 to 7 are 3-colorable (Borodin et al., 2005) and that planar graphs in which no triangles have common edges with cycles of length from 4 to 9 are 3-colorable (Borodin et al., 2006) . We give a common extension of these results by proving that every planar graph in which no triangles have common edges with -cycles, where (or, which is equivalent, with cycles of length 3, 5 and 7), is 3-colorable. [ABSTRACT FROM AUTHOR]

Abstract: We consider edge critical graphs when playing cops and robber. Specifically, we look at those graphs whose copnumbers change from one to two when any edge is added, deleted, subdivided or contracted. We characterize all such sets, showing that they are empty, trees, all 2-edge-connected graphs and empty, respectively. We also consider those graphs which change from copnumber two to one when any edge is added, and give a characterization in the k-regular case. [Copyright &y& Elsevier]

Abstract: We theoretically analyze the ‘cops and robber’ game for the first time in a multidimensional grid. It is shown that in an -dimensional grid, at least cops are necessary if one wants to catch the robber for all possible initial configurations. We also present a set of cop strategies for which cops are provably sufficient to catch the robber. Further, we revisit the game in a two-dimensional grid and provide an independent proof of the fact that the robber can be caught even by a single cop under certain conditions. [ABSTRACT FROM AUTHOR]

Abstract: A block-colouring of a -cycle system of order is a mapping , where is a set of colours. A partition of degree into parts defines a colouring of type in which the blocks containing a vertex are coloured exactly with colours. For a vertex and for , is the set of all the blocks incident with and coloured with colour . A colouring of type is equitable if, for every vertex , , for all . In this paper the authors continue the research begun in Gionfriddo et al. (2010) , where in particular they had studied tricolourings with three colours. Here the authors study tricolourings, i.e. equitable colourings of type , for -cycle systems and, in particular, they give complete results for -systems and for -systems, by proving that , and for the tricolourings with four colours. [Copyright &y& Elsevier]

Abstract: For a graph , let and denote the maximum cardinalities of packings of vertex-disjoint and edge-disjoint cycles of , respectively. We study the interplay of these two parameters and vertex cuts in graphs. If is a graph whose vertex set can be partitioned into three non-empty sets , , and such that there is no edge between and , and , then our results imply that is uniquely determined by the values for at most graphs of order at most , and is uniquely determined by the values for at most graphs of order at most . [Copyright &y& Elsevier]

Abstract: We investigate the expected value of various graph parameters associated with the minimum rank of a graph, including minimum rank/maximum nullity and related Colin de Verdière-type parameters. Let denote the usual Erdős-Rényi random graph on vertices with edge probability . We obtain bounds for the expected value of the random variables , , and , which yield bounds on the average values of these parameters over all labeled graphs of order . [Copyright &y& Elsevier]

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: There are only few results concerning crossing numbers of join of some graphs. In the paper, for the special graph on six vertices we give the crossing numbers of its join with isolated vertices as well as with the path on vertices and with the cycle . [Copyright &y& Elsevier]

Abstract: For a graph let denote the cyclomatic number and let denote the maximum number of edge-disjoint cycles of . We prove that for every there is a finite set such that every 2-connected graph for which arises by applying a simple extension rule to a graph in . Furthermore, we determine for exactly. [Copyright &y& Elsevier]

Abstract: We say that a hypergraph is hamiltonian path (cycle) saturated if does not contain an open (closed) hamiltonian chain but by adding any new edge we create an open (closed) hamiltonian chain in . In this paper we ask about the smallest size of an -uniform hamiltonian path (cycle) saturated hypergraph, mainly for . We present a construction of a family of 3-uniform path (cycle) saturated hamiltonian hypergraphs with edges. On the other hand we prove that the number of edges in an -uniform hamiltonian path (cycle) saturated hypergraph is at least . [Copyright &y& Elsevier]

Abstract: A graph is -critical if it is not -colourable but is -colourable for any edge . In this paper we show that for any integers and there exists a constant , such that for all , there exists a -critical graph on vertices with and odd girth at least , which can be made -colourable only by the omission of at least edges. [Copyright &y& Elsevier]

Abstract: Given a graph and sets of allowed colors for each , a list coloring of is an assignment of colors to the vertices, such that for all and for all . The choice number of is the smallest natural number admitting a list coloring for whenever holds for every vertex . This concept has an interesting variant, called Hall number, where an obvious necessary condition for colorability is put as a restriction on the lists . (On complete graphs, this condition is equivalent to the well-known one in Hall’s Marriage Theorem.) We prove that vertex deletion or edge insertion in a graph of order may make the Hall number decrease by as much as . This estimate is tight for all . Tightness is deduced from the upper bound that every graph of order has Hall number at most . We also characterize the cases of equality; for these are precisely the graphs whose complements are , , and . Our results completely solve a problem raised by Hilton, Johnson and Wantland [A.J.W. Hilton, P.D. Johnson, Jr., E. B. Wantland, The Hall number of a simple graph, Congr. Numer. 121 (1996), 161–182, Problem 7] in terms of the number of vertices, and strongly improve some estimates due to Hilton and Johnson [A.J.W. Hilton, P.D. Johnson, Jr., The Hall number, the Hall index, and the total Hall number of a graph, Discrete Appl. Math. 94 (1999), 227–245] as a function of maximum degree. [Copyright &y& Elsevier]

Abstract: It was proved in [Z. Dvořàk, D. Kràl, P. Nejedlỳ, R. Škrekovski, Coloring squares of planar graphs with girth six, European J. Combin. 29 (4) (2008) 838–849] that every planar graph with girth and maximum degree is 2-distance -colorable. We prove that every planar graph with and is 2-distance -colorable. [Copyright &y& Elsevier]

Abstract: Let be a simple graph with vertices, edges. Let and be the maximum and minimum degree of , respectively. If each edge of belongs to triangles (), then we present a new upper bound for the Laplacian spectral radius of as follows: Moreover, we give an example to illustrate that our result is, in some cases, the best. [Copyright &y& Elsevier]

Abstract: A homomorphism of a graph to a graph is a mapping from the vertex set of to the vertex set of which preserves edges. In this paper we provide an algorithm to determine the number of homomorphisms from an arbitrary finite undirected path to another arbitrary finite undirected path. [Copyright &y& Elsevier]

Abstract: We consider the game of Cops and Robbers played on finite and countably infinite connected graphs. The length of games is considered on cop-win graphs, leading to a new parameter, the capture time of a graph. While the capture time of a cop-win graph on vertices is bounded above by , half the number of vertices is sufficient for a large class of graphs including chordal graphs. Examples are given of cop-win graphs which have unique corners and have capture time within a small additive constant of the number of vertices. We consider the ratio of the capture time to the number of vertices, and extend this notion of capture time density to infinite graphs. For the infinite random graph, the capture time density can be any real number in . We also consider the capture time when more than one cop is required to win. While the capture time can be calculated by a polynomial algorithm if the number of cops is fixed, it is NP-complete to decide whether cops can capture the robber in no more than moves for every fixed . [Copyright &y& Elsevier]

Abstract: Symmetry of graphs has been extensively studied over the past fifty years by using automorphisms of graphs and group theory which have played and still play an important role for graph theory, and promising and interesting results have been obtained, see for examples, [L.W. Beineke, R.J. Wilson, Topics in Algebraic Graph Theory, Cambridge University Press, London, 2004; N. Biggs, Algebraic Graph Theory, Cambridge University Press, London, 1993; C. Godsil, C. Royle, Algebraic graph theory, Springer-Verlag, London, 2001; G. Hahn, G. Sabidussi, Graph Symmetry: Algebraic Methods and Application, in: NATO ASI Series C, vol. 497, Kluwer Academic Publishers, Dordrecht, 1997]. We introduced generalized symmetry of graphs and investigated it by using endomorphisms of graphs and semigroup theory. In this paper, we will survey some results we have achieved in recent years. The paper consists of the following sections. [1.] Introduction [2.] End-regular graphs [3.] End-transitive graphs [4.] Unretractive graphs [5.] Graphs and their endomorphism monoids. [Copyright &y& Elsevier]