Search

Let G be a simple connected graph and A (G) be its adjacency matrix. The terms singularity, eigenvalues, and characteristic polynomial of G mean those of A (G). A nonsingular graph G is said to have the reciprocal eigenvalue property if the reciprocal of each eigenvalue of G is also an eigenvalue. A graph G (possibly singular) is said to have the weak reciprocal eigenvalue property if the reciprocal of each nonzero eigenvalue of it is also an eigenvalue. In Barik et al. (2022) [3] , the authors proved that there is no nontrivial tree with the weak reciprocal eigenvalue property and posed the following question: "Does there exist a nontrivial graph with the weak reciprocal eigenvalue property?" Suppose that G is singular and the characteristic polynomial of G is x n − k (x k + a 1 x k − 1 + ⋯ + a k). Assume that A (G) has rank k , so that a k ≠ 0. Can we ever have | a k | = 1 ? The answer turns out to be negative. As an application, we settle the question posed in Barik et al. (2022) [3]. Another similar application is also mentioned. It is natural to wonder, "Does there exist a nontrivial, simple, connected weighted graph with the weak reciprocal eigenvalue property?" We provide a class of such graphs. Furthermore, we extend our results to weighted graphs. [ABSTRACT FROM AUTHOR]

A conjecture attributed to Smith states that every two longest cycles in a k -connected graph intersect in at least k vertices. In this paper, we show that every two longest cycles in a k -connected graph on n vertices intersect in at least min ⁡ { n , 8 k − n − 16 } vertices, which confirms Smith's conjecture when k ≥ (n + 16) / 7. An analog conjecture for paths instead of cycles was stated by Hippchen. By a simple reduction, we relate both conjectures, showing that Hippchen's conjecture is valid when either k ≤ 7 or k ≥ (n + 9) / 7. [ABSTRACT FROM AUTHOR]

Toughness implies the topological representation characterization of network graphs. The pioneering works implicated that there are salient relationship between toughness and the existence of fractional factor in various settings. Specifically, Liu and Zhang (2008) [7] determined that G admits a fractional k -factor if t (G) ≥ k − 1 k and | V (G) | ≥ k + 1 (k ≥ 2 is an integer), and the toughness bound is tight. A graph G is fractional (k , n) -critical, if removing any n vertices from G the resulting subgraph still admits a fractional k -factor. In this paper, we prove that if k > n , then the original toughness condition (i.e., t (G) ≥ k − 1 k) is sufficient for a graph to be fractional (k , n) -critical. Furthermore, we explain why k > n is the extreme boundary to keep the original toughness bound. [ABSTRACT FROM AUTHOR]

Let α ∈ [ 0 , 1) , and let G be a connected graph of order n with n ≥ f (α) , where f (α) = 14 for α ∈ [ 0 , 1 2 ] , f (α) = 17 for α ∈ (1 2 , 2 3 ] , f (α) = 20 for α ∈ (2 3 , 3 4 ] and f (α) = 5 1 − α + 1 for α ∈ (3 4 , 1). A spanning subgraph whose components are paths is said to be a path-factor. A P ≥ k -factor means a path-factor with each component being a path of order at least k , where k ≥ 2 is an integer. The A α -spectral radius of G is denoted by ρ α (G). In this paper, it is verified that G has a P ≥ 2 -factor if ρ α (G) > θ (n) , where θ (n) is the largest root of x 3 − ((α + 1) n + α − 5) x 2 + (α n 2 + (α 2 − 3 α − 1) n − 2 α + 1) x − α 2 n 2 + (7 α 2 − 5 α + 3) n − 18 α 2 + 29 α − 15 = 0. Furthermore, we provide a graph to show that the bound on A α -spectral radius is optimal. [ABSTRACT FROM AUTHOR]

Let G be a connected graph and let k be a positive integer. Let T be a spanning tree of G. The leaf degree of a vertex v ∈ V (T) is defined as the number of leaves adjacent to v in T. The leaf degree of T is the maximum leaf degree among all the vertices of T. Let D (G) and Q (G) denote the distance matrix and the distance signless Laplacian matrix of G , respectively. In this work, we provide the upper bounds for the spectral radius of D (G) (resp. Q (G)) in a connected graph G of order n to guarantee that G contains a spanning tree with leaf degree at most k. Furthermore, we establish some extremal graphs to show all the upper bounds obtained in this work are sharp. [ABSTRACT FROM AUTHOR]

For a non-decreasing sequence of integers (a 1 , a 2 , ... , a k) , an (a 1 , a 2 , ... , a k) -packing coloring of a graph G is a partition of V (G) into k subsets V 1 , V 2 , ... , V k such that the distance between any two distinct vertices x , y ∈ V i is at least a i + 1 , 1 ≤ i ≤ k. This paper studies the packing coloring of subcubic graphs. Gastineau and Togni (2016) [7] asked whether every subcubic graph except the Petersen graph is (1 , 1 , 2 , 3) -packing colorable. A subcubic graph G is said to be i -saturated, 0 ≤ i ≤ 2 , if every vertex of degree three in G has at most i neighbors of degree three and it is said to be 3-saturated if it is not 2-saturated. Besides, a vertex of degree three in a 3-saturated subcubic graph is said to be heavy if all its neighbors are of degree three. We prove that every 1-saturated subcubic graph is (1 , 1 , 2) -packing colorable. Moreover, we prove that a 3-saturated subcubic graph is (1 , 1 , 2 , 2) -packing colorable if any two of its heavy vertices are not adjacent. [ABSTRACT FROM AUTHOR]

A matrix A is said to be an integer matrix if all its entries are integers. In this article, we characterize the nonsingular integer matrices with integer eigenvalues in an expressible form of their corresponding inverse matrices. It is proved that a nonsingular integer matrix A has integer eigenvalues if and only if A − 1 can be written as the sum of n rank-one matrices that meet certain requirements. A method for constructing integer matrices with integer eigenvalues using the Hadamard product is also provided. Let S represent an n -tuple of nonnegative integers. If there is an n × n integer matrix A whose spectrum (the collection of eigenvalues) is S , we say that S is realisable by an integer matrix. In Fallat et al. (2005) [7] , the authors posed a conjecture that " there is no simple graph on n ≥ 2 vertices whose Laplacian spectrum is given by (0 , 1 , ... , n − 1)." We provide a characterization of threshold graphs using the spectra of quotient matrices of its G -join graphs. As a consequence, we prove that given any n − 1 positive integers λ 2 , ... , λ n such that λ 2 ≤ ⋯ ≤ λ n , the n -tuple (0 , λ 2 , ... , λ n) is realizable by the Laplacian matrix of a multidigraph. In particular, we show that (0 , 1 , ... , n − 1) can be realizable by the Laplacian matrix of a multidigraph. [ABSTRACT FROM AUTHOR]

This paper generalizes and unifies the existing spectral bounds on the k -independence number of a graph, which is the maximum size of a set of vertices at pairwise distance greater than k. The previous bounds known in the literature follow as a corollary of the main results in this work. We show that for most cases our bounds outperform the previous known bounds. Some infinite families of graphs where the bounds are tight are also presented. Finally, as a byproduct, we derive some spectral lower bounds for the diameter of a graph. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph with n vertices and m edges. The spectral radius ρ (G) of G is the largest eigenvalue of its adjacency matrix. In this paper, we firstly consider the effect on the spectral radius of a graph by removing a vertex, and then as an application of the result, we obtain a new sharp upper bound of ρ (G) which improves some known bounds: If (k − 2) (k − 3) 2 ≤ m − n ≤ k (k − 3) 2 , where k (3 ≤ k ≤ n) is an integer, then ρ (G) ≤ 2 m − n − k + 5 2 + 2 m − 2 n + 9 4 . The equality holds if and only if G is a complete graph K n or K 4 − e , where K 4 − e is the graph obtained from K 4 by deleting some edge e. [ABSTRACT FROM AUTHOR]

In this article, we obtain a sufficient condition related to toughness τ (G) for a graph to be all fractional (a , b , k) -critical. We prove that if τ (G) ≥ (b 2 − 1) + a k a for some nonnegative integers a , b , k , then G is all fractional (a , b , k) -critical. Our result improves the known results in Liu and Zhang (2008) and Liu and Cai (2009). [ABSTRACT FROM AUTHOR]

A well-known conjecture of Grünbaum (1970) and Nash-Williams (1971) asserts that every 4-connected toroidal graph has a Hamiltonian cycle. Related to this conjecture, Kawarabayashi and Ozeki (2011) proved two results on a 2-factor and a 3-factor. In this paper, motivated by these results, we give several sufficient conditions for a graph embedded in a surface to have an [ a , b ] -factor. We also show that several conditions are best possible. [ABSTRACT FROM AUTHOR]

Abstract A path decomposition of a graph G is a collection of edge-disjoint paths of G that covers the edge set of G. Gallai (1968) conjectured that every connected graph on n vertices admits a path decomposition of cardinality at most ⌊ (n + 1) ∕ 2 ⌋. Gallai's Conjecture has been verified for many classes of graphs. In particular, Lovász (1968) verified this conjecture for graphs with at most one vertex with even degree, and Pyber (1996) verified it for graphs in which every cycle contains a vertex with odd degree. Recently, Bonamy and Perrett (2016) verified Gallai's Conjecture for graphs with maximum degree at most 5, and Botler et al. (2017) verified it for graphs with treewidth at most 3. In this paper, we verify Gallai's Conjecture for triangle-free planar graphs. [ABSTRACT FROM AUTHOR]

Abstract The fixing number of a graph Γ is the minimum number of labeled vertices that, when fixed, remove all nontrivial automorphisms from the automorphism group of Γ. The fixing set of a finite group G is the set of all fixing numbers of graphs whose automorphism groups are isomorphic to G. Previously, authors have studied the fixing sets of both abelian groups and symmetric groups. In this article, we determine the fixing set of the dihedral group. [ABSTRACT FROM AUTHOR]

In this paper we introduce the graph Γ s c (G) associated with a group G , called the solvable conjugacy class graph (abbreviated as SCC-graph), whose vertices are the nontrivial conjugacy classes of G and two distinct conjugacy classes C , D are adjacent if there exist x ∈ C and y ∈ D such that 〈 x , y 〉 is solvable. We discuss the connectivity, girth, clique number, and several other properties of the SCC-graph. One of our results asserts that there are only finitely many finite groups whose SCC-graph has given clique number d , and we find explicitly the list of such groups with d = 2. We pose some problems on the relation of the SCC-graph to the solvable graph and to the NCC-graph, which we cannot solve. [ABSTRACT FROM AUTHOR]

A k -independent set in a connected graph is a set of vertices such that any two vertices in the set are at distance greater than k in the graph. The k -independence number of a graph, denoted α k , is the size of a largest k -independent set in the graph. Recent results have made use of polynomials that depend on the spectrum of the graph to bound the k -independence number. They are optimized for the cases k = 1 , 2. There are polynomials that give good (and sometimes) optimal results for general k , including case k = 3. In this paper, we provide the best possible bound that can be obtained by choosing a polynomial for case k = 3 and apply this bound to well-known families of graphs including the Hamming graph. [ABSTRACT FROM AUTHOR]

The independence polynomial i ( G , x ) of a graph G is the generating function of the numbers of independent sets of each size. A graph of order n is very well-covered if every maximal independent set has size n ∕ 2 . Levit and Mandrescu conjectured that the independence polynomial of every very well-covered graph is unimodal (that is, the sequence of coefficients is nondecreasing, then nonincreasing). In this article we show that every graph is embeddable as an induced subgraph of a very well-covered graph whose independence polynomial is unimodal, by considering the location of the roots of such polynomials. [ABSTRACT FROM AUTHOR]

Let k be a positive integer. In this paper, we prove that for a graph G with at least 4 k vertices, if max { d ( x ) , d ( y ) } ≥ 2 k for any pair of nonadjacent vertices { x , y } ⊆ V ( G ) , then G contains k disjoint cycles. This generalizes the results given by Corr á di and Hajnal (1963), Enomoto (1998), and Wang (1999). [ABSTRACT FROM AUTHOR]

In this paper, we study the relationship between the radius r and the attachment number a of a tetravalent graph admitting a half-arc-transitive group of automorphisms. These two parameters were first introduced in Marušič (1998), where among other things it was proved that a always divides 2 r . Intrigued by the empirical data from the census (Potočnik et al., 2015) of all such graphs of order up to 1000 we pose the question of whether all examples for which a does not divide r are arc-transitive. We prove that the answer to this question is positive in the case when a is twice an odd number. In addition, we completely characterise the tetravalent graphs admitting a half-arc-transitive group with r = 3 and a = 2 , and prove that they arise as non-sectional split 2 -fold covers of line graphs of 2 -arc-transitive cubic graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple graph and let G ‾ denote its complement. We say that G is integral if its spectrum consists entirely of integers. Let G a and G b be two regular integral graphs of order p and q and degree a and b , respectively. In this work we establish a characterization of integral graphs which belong to the class α G a ∪ β G b ‾ , where mG denotes the m -fold union of the graph G. In particular, (i) we demonstrate that there exists no integral graph from the class α G a ∪ β G a − 1 ‾ for α , β , a , p , q ∈ N and (ii) we demonstrate that if α G a ∪ β G b ‾ is integral with b = a − 2 then it belongs to the class of integral graphs (x 0 + q z) G 2 a ∪ (y 0 + p z) G 2 a − 2 ‾ , where (i) a , p , q ∈ N so that 2 a ≤ p − 1 , 2 a − 2 ≤ q − 1 and (p , q) = 1 ; (i i) (x 0 , y 0) is a particular solution of the linear Diophantine equation p x − q y = 1 and (i i i) z ≥ z 0 where z 0 is the least integer such that (x 0 + q z 0) ≥ 1 and (y 0 + p z 0) ≥ 1. [ABSTRACT FROM AUTHOR]

In this paper, we consider the classification of nonorientable regular embeddings of cartesian products G d of a graph G . We show that if G is a bipartite graph and d ≥ 3 , then there is no nonorientable regular embedding. This is a generalization of the result that there is no nonorientable regular embeddings of Q n for n ≥ 3 shown by R. Nedela and the author in 2007. When G is non-bipartite and d ≥ 3 , we show that if there is a nonorientable regular embedding of G d , then there is a nonorientable regular embedding of G . Furthermore, we show that any nonorientable regular embedding of G d with d ≥ 3 is isomorphic to a Petrie dual of some orientable regular embedding of G d . Using these results, we classify the nonorientable regular embeddings of cartesian products C n d of a cycle C n ; for even n there is no nonorientable regular embedding except when d = 1 , and for odd n there is a unique nonorientable regular embedding for each d . [ABSTRACT FROM AUTHOR]

In this paper, we prove that for any positive integer k and for any simple graph G of order at least 3 k , if d ( x ) + d ( y ) ≥ 4 k for every pair of vertices x and y of distance 2 in G , then with one exception, G contains k disjoint cycles. This generalizes a former result of Corrádi and Hajnal (1963). [ABSTRACT FROM AUTHOR]

Given a non-decreasing sequence S = ( s 1 , s 2 , … , s k ) of positive integers, an S - packing coloring of a graph G is a mapping c from V ( G ) to { s 1 , s 2 , … , s k } such that any two vertices with the i th color are at mutual distance greater than s i , 1 ≤ i ≤ k . This paper studies S -packing colorings of (sub)cubic graphs. We prove that subcubic graphs are ( 1 , 2 , 2 , 2 , 2 , 2 , 2 ) -packing colorable and ( 1 , 1 , 2 , 2 , 2 ) -packing colorable. For subdivisions of subcubic graphs we derive sharper bounds, and we provide an example of a cubic graph of order 38 which is not ( 1 , 2 , … , 12 ) -packing colorable. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and let S k (G) be the sum of the first k largest Laplacian eigenvalues of G. It was conjectured by Brouwer in 2006 that S k (G) ≤ e (G) + ( k + 1 2 ) holds for 1 ≤ k ≤ n − 1. The case k = 2 was proved by Haemers, Mohammadian and Tayfeh-Rezaie [Linear Algebra Appl., 2010]. In this paper, we propose the full Brouwer's Laplacian spectrum conjecture and we prove the conjecture holds for k = 2 which also confirm the conjecture of Guan et al. in 2014. [ABSTRACT FROM AUTHOR]

Let G be a finite, simple, undirected graph with vertex set V ( G ) and F be a family of graphs. A subgraph of G is F -free if it does not contain any graph of F as induced subgraph. In this paper, we present lower bounds on the maximum weight w ( H ) = ∑ i ∈ V ( H ) w i of an F -free induced subgraph H of G , where w i > 0 denotes the weight of a vertex i ∈ V ( G ) . [ABSTRACT FROM AUTHOR]

Recently normalized Laplacian matrices of graphs are studied as density matrices in quantum mechanics. Separability and entanglement of density matrices are important properties as they determine the nonclassical behavior in quantum systems. In this note we look at the graphs whose normalized Laplacian matrices are separable or entangled. In particular, we show that the number of such graphs is related to the number of 0–1 matrices that are line sum symmetric and to the number of graphs with at least one vertex of degree 1. [ABSTRACT FROM AUTHOR]

The aim of the paper is to find discrete versions of the Wiman theorem which states that the maximum possible order of an automorphism of a Riemann surface of genus g ≥ 2 is 4 g + 2 . The role of a Riemann surface in this paper is played by a finite connected graph. The genus of a graph is defined as the rank of its homology group. Let Z N be a cyclic group acting freely on the set of directed edges of a graph X of genus g ≥ 2 . We prove that N ≤ 2 g + 2 . The upper bound N = 2 g + 2 is attained for any even g . In this case, the signature of the orbifold X / Z N is ( 0 ; 2 , g + 1 ) , that is X / Z N is a tree with two branch points of order 2 and g + 1 respectively. Moreover, if N < 2 g + 2 , then N ≤ 2 g . The upper bound N = 2 g is attained for any g ≥ 2 . The latter takes a place when the signature of the orbifold X / Z N is ( 0 ; 2 , 2 g ) . [ABSTRACT FROM AUTHOR]

Let G be a simple graph with n (G) vertices and e (G) edges. Denoted by η (G) and m ⁎ (G) the nullity and the fractional matching number of G , respectively. The dimension of cycle space of G is defined as c (G) = e (G) − n (G) + ω (G) , where ω (G) denotes the number of connected components of G. In this paper, we prove that n (G) − 2 m ⁎ (G) ≤ η (G) ≤ n (G) − 2 m ⁎ (G) + 2 c (G) for a graph G , which improves the main results of Wang and Wong (2014) [19] and Ma and Fang (2019) [11] , respectively. Furthermore, all graphs with nullity η (G) = n − 2 m ⁎ (G) + 2 c (G) are determined. We also prove that there is no graph with nullity η (G) = n − 2 m ⁎ (G) + 2 c (G) − 1 ; and for fixed c (G) , infinitely many connected graphs with nullity n − 2 m ⁎ (G) + 2 c (G) − k (0 ≤ k ≤ 2 c (G) , k ≠ 1) are also constructed. As an application of the above results, we also prove that if G is nonsingular, then G has a fractional perfect matching. [ABSTRACT FROM AUTHOR]

For a finite sequence of positive integers to be the degree sequence of a finite graph, Zverovich and Zverovich gave a sufficient condition involving only the length of the sequence, its largest entry and its smallest entry. Barrus, Hartke, Jao, and West gave a better bound and showed that the sharp bound is never less than theirs by more than 1. In this paper we determine the sharp bound. [ABSTRACT FROM AUTHOR]

Let us fix a function f ( n ) = o ( n ln n ) and real numbers 0 ≤ α < β ≤ 1 . We present a polynomial time algorithm which, given a directed graph G with n vertices, decides either that one can add at most β n new edges to G so that G acquires a Hamiltonian circuit or that one cannot add α n or fewer new edges to G so that G acquires at least e − f ( n ) n ! Hamiltonian circuits, or both. [ABSTRACT FROM AUTHOR]

We establish conditions for a permutation group generated by a single permutation of a prime power order to be an automorphism group of a graph or an edge-colored graph. This corrects and generalizes the results of the two papers on cyclic permutation groups published in 1978 and 1981 by S. P. Mohanty, M. R. Sridharan, and S. K. Shukla. [ABSTRACT FROM AUTHOR]

Let G be a connected non-bipartite graph on n vertices with domination number γ≤n+1/3. We present a lower bound for the least eigenvalue of the signless Laplacian of G in terms of the domination number. [ABSTRACT FROM AUTHOR]

Abstract: Let be a graph with vertices and edges. Also let be the eigenvalues of the Laplacian matrix of graph . The Laplacian energy of the graph is defined as In this paper, we present some lower and upper bounds for of graph in terms of , the number of edges and the maximum degree . Also we give a Nordhaus–Gaddum-type result for Laplacian energy of graphs. Moreover, we obtain a relation between Laplacian energy and Laplacian-energy-like invariant of graphs. [Copyright &y& Elsevier]

Abstract: Graph coverings are known to induce surjections of their critical groups. Here we describe the kernels of these morphisms in terms of data parametrizing the covering. Regular coverings are parametrized by voltage graphs, and the above kernel can be identified with a naturally defined voltage graph critical group. For double covers, the voltage graph is a signed graph, and the theory takes a particularly pleasant form, leading also to a theory of double covers of signed graphs. [Copyright &y& Elsevier]

Abstract: Under mild restrictions, we characterize all ways in which an incidence graph of a biaffine plane over a finite field can be extended to a vertex-transitive graph of diameter 2 and a given degree with a comparatively large number of vertices. [Copyright &y& Elsevier]

Abstract: The rainbow connection number of a graph is the least number of colours in a (not necessarily proper) edge-colouring of such that every two vertices are joined by a path which contains no colour twice. Improving a result of Caro et al., we prove that the rainbow connection number of every 2-connected graph with vertices is at most . The bound is optimal. [Copyright &y& Elsevier]

Given a set S , and any selfmap f : S → S , the functional graph associated with f can be described as a graph with vertex set S and directed edge set E = { (u , v) ∈ S 2 : f (u) = v }. A classification of all functional graphs induced by lattice endomorphisms has been done by Szigeti ([3]). In this paper, we aim to achieve a similar type of classification with respect to functional graphs induced by endomorphisms of certain abelian groups. [ABSTRACT FROM AUTHOR]

Abstract: Which graphs admit an integer valued harmonic function which is injective and surjective onto ? Such a function, which we call harmonic labeling, is constructed when the graph is the lattice . It is shown that for any finite graph containing at least one edge, there is no harmonic labeling of . Further discussion and open problems are presented. [Copyright &y& Elsevier]

Abstract: The power of a graph , denoted by , is the graph with the same vertex set as , such that two vertices are adjacent in if and only if their distance is at most in . In this paper, we give bounds on the first two largest Laplacian eigenvalues of the second power of a general graph, and on the second power of a tree. We also give a Nordhaus–Gaddum-type inequality for the Laplacian spectral radius of . [Copyright &y& Elsevier]

Abstract: The exact crossing number is known only for a few specific families of graphs. Cartesian products of two graphs belong to the first families of graphs for which the crossing number has been studied. Let be a path with vertices. , the -power of the graph , is a graph on the same vertex set as and the edges that join two vertices of if the distance between them is at most . Very recently, some results concerning crossing numbers of were obtained. In this paper, the crossing numbers of the Cartesian product of with the cycle are studied. It is proved that the crossing number of the graph is , and the upper bound for the crossing number of the graph is given. [Copyright &y& Elsevier]

Abstract: A -subtrestle in a graph is a 2-connected subgraph of of maximum degree at most . We prove a lower bound on the order of a largest -subtrestle of in terms of and the minimum degree of . A corollary of our result is that every 2-connected graph with vertices and minimum degree at least contains a spanning -subtrestle. This corollary is an extension of Dirac’s theorem. [Copyright &y& Elsevier]

Abstract: The reconstruction number of a graph is the smallest number of vertex-deleted subgraphs needed to uniquely determine the graph up to isomorphism. Bollobás showed that almost all graphs have reconstruction number equal to three. McMullen and Radziszowski published a catalogue of all graphs on at most ten vertices with reconstruction number greater than three. We introduce constructions that generalize the examples identified in their work. In particular, we use lexicographic products of vertex transitive graphs with certain starter graphs from the work of Myrvold and from the work of Harary and Plantholt to generate new infinite families of graphs with high reconstruction numbers. In the process, we settle a question of McMullen and Radziszowski. [Copyright &y& Elsevier]

Abstract: Let denote the undirected path of length . The cardinality of the set of congruence classes induced by the graph homomorphisms from onto is determined. This settles an open problem of Michels and Knauer [M. A. Michels, U. Knauer, The congruence classes of paths and cycles, Discrete Mathematics, 309 (2009) 5352–5359]. Our result is based on a new proven formula of the number of homomorphisms between paths. [Copyright &y& Elsevier]

Abstract: Let be a simple graph. Denote by the diagonal matrix of its vertex degrees and by its adjacency matrix. Then the signless Laplacian matrix of is . In , Cvetković et al. (2007) have given conjectures on signless Laplacian eigenvalues of (see also Aouchiche and Hansen (2010) , Oliveira et al. (2010) ). Here we prove two conjectures. [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: 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: We provide a proof of Sholander’s claim [M. Sholander, Trees, lattices, order, and betweenness, Proceedings of the American Mathematical Society 3 (1952) 369–381] concerning the representability of collections of so-called segments by trees, which yields a characterization of the interval function of a tree. Furthermore, we streamline Burigana’s characterization [L. Burigana, Tree representations of betweenness relations defined by intersection and inclusion, Mathematics and Social Sciences 185 (2009) 5–36] of tree betweenness and provide a relatively short proof. [Copyright &y& Elsevier]

Abstract: Bertrand, Charon, Hudry and Lobstein studied, in their paper in 2004 , -locating–dominating codes in paths . They conjectured that if is a fixed integer, then the smallest cardinality of an -locating–dominating code in , denoted by , satisfies for infinitely many values of . We prove that this conjecture holds. In fact, we show a stronger result saying that for any we have for all when is large enough. In addition, we solve a conjecture on location–domination with segments of even length in the infinite path. [Copyright &y& Elsevier]

Abstract: It has recently been shown that infinite matroids can be axiomatized in a way that is very similar to finite matroids and permits duality. This was previously thought impossible, since finitary infinite matroids must have non-finitary duals. In this paper we illustrate the new theory by exhibiting its implications for the cycle and bond matroids of infinite graphs. We also describe their algebraic cycle matroids, those whose circuits are the finite cycles and double rays, and determine their duals. Finally, we give a sufficient condition for a matroid to be representable in a sense adapted to infinite matroids. Which graphic matroids are representable in this sense remains an open question. [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]