Search

We investigate a multi-stage newsvendor problem with advance purchase discount (APD) in this paper. At the beginning of a stage, the decision maker (DM) makes the advance ordering decision for all the periods in this stage; at the start of every period within the stage, the DM makes the regular ordering decision. In this problem, the only available information we can observe is the past demands. To solve this problem, we extend the weak aggregating algorithm (WAA) with one decision variable, an online learning approach based on the theory of prediction and learning with expert advice, to a two-dimensional problem that involves advance ordering decisions in stages and regular ordering decisions nested in each stage. The difficulty of the problem lies in transferring learned knowledge of demand information from stage to stage. We design a cross-stage knowledge transfer scheme and obtain online ordering solutions for both advance-order and regular-order. We show that our solutions converge to the optimal solutions asymptotically. In addition, we derive theoretical guarantees for total gains in one stage and cumulative gains for all stages in the planning horizon. Through numerical studies, we find that our solutions are competitive to those offered by the best experts in hindsight. Finally, we do the sensitivity analysis to illustrate the effectiveness of our algorithm under different parameter values. • Consider advance purchase discounts in a multi-stage newsvendor problem. • Extend weak aggregating algorithm from one- to a two-dimensional case. • Obtain analytical solutions for both advance order and regular order. • Derive theoretical guarantees for one stage and all stages' profits. [ABSTRACT FROM AUTHOR]

The energy of a graph G , denoted by E (G) , is defined as the sum of the absolute values of all eigenvalues of G. In this paper we study the difference of energies of a (regular) graph G and its complete graph G ‾ , that is, E (G) − E (G ‾). In particular, we provide the answer to Problem 12 raised in Nikiforov (2016) [18]. Moreover, we give a lower bound for the energy of a regular graph in terms of the order and the clique cover number. [ABSTRACT FROM AUTHOR]

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MaxCut) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and achieves an approximation ratio of at least 1 2 in expectation. When the graph is d -regular and triangle-free, a slightly better approximation ratio can be achieved with a randomized algorithm running in a single round. Here, we investigate the round complexity of deterministic distributed algorithms for MaxCut in regular graphs. We first prove that if G is d -regular, with d even and fixed, no deterministic algorithm running in a constant number of rounds can achieve a constant approximation ratio. We then give a simple one-round deterministic algorithm achieving an approximation ratio of 1 d for d -regular graphs when d is odd. We show that this is best possible in several ways, and in particular no deterministic algorithm with approximation ratio 1 d + ϵ (with ϵ > 0) can run in a constant number of rounds. We also prove results of a similar flavor for the MaxDiCut problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part to the right part of the cut. [ABSTRACT FROM AUTHOR]

A proper edge-coloring of a graph with positive integers is an interval coloring if the colors on the edges incident to any vertex are consecutive. It is NP-complete to determine whether a graph has an interval coloring. In this paper, we obtain several sufficient conditions for complete tripartite graphs to have interval colorings, particularly considering the case of complete tripartite graphs where one part has size 2. We also obtain two results on interval colorings of (a , b) -biregular graphs by extending known proof techniques, where a bipartite graph is (a , b) -biregular if every vertex in one part has degree a and every vertex in the other part has degree b. It has been conjectured that all such graphs have interval colorings. [ABSTRACT FROM AUTHOR]

Let G be a graph with an even number of vertices. The matching preclusion number of G , denoted by m p (G) , is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching. G is maximally matched if m p (G) is equal to the minimum degree of G and is super matched if every optimal matching preclusion set of G consists of edges incident to a single vertex. In this paper, we focus on matching preclusion for direct product of graphs. For any two graphs G and H , we denote their direct product by G × H and show m p (G × H) ⩾ m p (G) m p (H) , which implies that the direct product of two maximally matched graphs is also maximally matched. Furthermore, for any two regular graphs with at least three vertices, we show that if at least one of them is maximally matched, then their direct product is super matched, and as a consequence, their strong product is also super matched. [ABSTRACT FROM AUTHOR]

In this paper, we consider the distance-regular graphs Γ whose distance-2 graphs Γ 2 are strongly regular. Note that if Γ is bipartite, then its distance-2 graph is not connected. We first show that the distance-2 graph of a non-bipartite distance-regular graph with diameter 3 and eigenvalue a 2 − c 3 is strongly regular, and then we give several kinds of classifications of non-bipartite distance-regular graphs with diameter 3 and eigenvalue a 2 − c 3. [ABSTRACT FROM AUTHOR]

Fault diagnosis capability is an important metric of the reliability of multiprocessor systems. The h -edge tolerable diagnosability is the maximum number of faulty nodes that the system can guarantee to locate when the number of faulty links does not exceed h. In fact, the 0-edge tolerable diagnosability is exactly the traditional diagnosability. In this paper, we determine the h -edge tolerable diagnosabilities of triangle-free graphs under the PMC model and the MM⁎ model, respectively, which extend the results of triangle-free regular graphs (Wei and Xu (2019) [26]). As applications, the h -edge tolerable diagnosabilities of many networks are determined under the PMC model and the MM⁎ model. [ABSTRACT FROM AUTHOR]

In this paper we consider a concept of strong regularity of signed graphs—a generalization of strong regularity of graphs. We establish certain structural and spectral properties of such signed graphs and determine or characterize those belonging to specified classes. Theoretical results are followed by examples and discussions. [ABSTRACT FROM AUTHOR]

The energy of a graph G , E (G) , is the sum of absolute values of the eigenvalues of its adjacency matrix. Gutman et al. proved that for every cubic graph of order n , E (G) ≥ n. Here, we improve this result by showing that if G is a connected subcubic graph of order n ≥ 8 , then E (G) ≥ 1.01 n. Also, we prove that if G is a traceable subcubic graph of order n ≥ 8 , then E (G) > 1.1 n. Let G be a connected cubic graph of order n ≥ 8 , it is shown that E (G) > n + 2. It was proved that if G is a connected cubic graph of order n , then E (G) ≤ 1.65 n. Also, in this paper we would like to present the best lower bound for the energy of a connected cubic graph. We introduce an infinite family of connected cubic graphs whose for each element of order n , say G , E (G) ≥ 1.24 n , and conjecture that if 6 | n , then minimum energy occurs just for each element of this family. We conjecture that there exists N such that for every connected cubic graph G of order n ≥ N , E (G) ≥ 1.24 n. [ABSTRACT FROM AUTHOR]

In this paper we explore some results concerning the spread of the line and the total graph of a given graph. A sufficient condition for the spread of a unicyclic graph with an odd girth to be at most the spread of its line graph is presented. Additionally, we derive an upper bound for the spread of the line graph of graphs on n vertices having a vertex (edge) connectivity at most a positive integer k. Combining techniques of interlacing of eigenvalues, we derive lower bounds for the Laplacian and signless Laplacian spread of the total graph of a connected graph. Moreover, for a regular graph, an upper and lower bound for the spread of its total graph is given. [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n and let μ be an adjacency eigenvalue with multiplicity k ≥ 1. A star complement H for μ in G is an induced subgraph of order n − k with no eigenvalue μ. In this paper, the regular graphs with the complete multipartite graph s K 1 ∪ ˙ K t ‾ (s ≥ 2) as a star complement are investigated. More precisely, when μ is a main eigenvalue, we prove that G = K s + 2. When μ is a non-main eigenvalue, we determine the regular graphs with s K 1 ∪ ˙ K t ‾ as a star complement for t = 1 or s = 3. We show that the complete multipartite graph (s + 1) K 2 ‾ (s ≥ 2) is the only possible graph under a certain condition, and we raise a conjecture for the general case. [ABSTRACT FROM AUTHOR]

Let κ (G) , μ n − 1 (G) , λ 2 (G) and q 2 (G) denote the vertex-connectivity, the algebraic connectivity, the second largest adjacency eigenvalue, and the second largest signless Laplacian eigenvalue of G , respectively. In this paper, we prove that for an integer k > 0 and any simple graph G of order n with maximum degree Δ and minimum degree δ ≥ k , the vertex-connectivity κ (G) ≥ k if μ n − 1 (G) > H 2 (Δ , δ , k) or λ 2 (G) < δ − H 2 (Δ , δ , k) or q 2 (G) < 2 δ − H 2 (Δ , δ , k) , where H 2 (Δ , δ , k) = (k − 1) n Δ (n − k + 1) (k − 1) + 4 (δ − k + 2) (n − δ − 1) , which improves the result in [Appl. Math. Comput. 344–345 (2019) 141–149] and the result in [Electron. J. Linear Algebra 34 (2018) 428–443]. Analogue results involving μ n − 1 (G) , λ 2 (G) and q 2 (G) to characterize vertex-connectivity of regular graphs, triangle-free graphs and graphs with fixed girth are also presented. [ABSTRACT FROM AUTHOR]

A (k , g) -graph is a k -regular graph with girth g and a (k , g) -cage is a (k , g) -graph with the fewest possible number of vertices n (k , g). Constructing (k , g) -cages and determining the order are both very hard problems. For this reason, an intensive line of research is devoted to constructing smaller (k , g) -graphs than previously known ones, providing in this way new upper bounds to n (k , g) each time such a graph is constructed. The paper focuses on girth g = 5 , where cages are known only for degrees k ≤ 7. We construct (k , 5) -graphs using and extending techniques of amalgamation into the incidence graphs of elliptic semiplanes of type L introduced and exposed by Funk (2009). The order of these graphs provides better upper bounds on n (k , 5) than those known so far, for values of k such that either 13 ≤ k ≤ 33 or k ≥ 66. [ABSTRACT FROM AUTHOR]

We study the behavior of the 2-rank of the adjacency matrix of a graph under Seidel and Godsil–McKay switching, and apply the result to graphs coming from graphical Hadamard matrices of order 4 m. Starting with graphs from known Hadamard matrices of order 64, we find (by computer) many Godsil–McKay switching sets that increase the 2-rank. Thus we find strongly regular graphs with parameters (63 , 32 , 16 , 16) , (64 , 36 , 20 , 20) , and (64 , 28 , 12 , 12) for almost all feasible 2-ranks. In addition we work out the behavior of the 2-rank for a graph product related to the Kronecker product for Hadamard matrices, which enables us to find many graphical Hadamard matrices of order 4 m for which the number of related strongly regular graphs with different 2-ranks is unbounded as a function of m. The paper extends results from the article 'Switched symplectic graphs and their 2-ranks' by the first and the last author. [ABSTRACT FROM AUTHOR]

Let τ (G) and κ ′ (G) denote the spanning tree packing number and the edge-connectivity of a graph G , respectively. Cioabă and Wong (2012) in [5] conjectured an explicit relationship between τ (G) and the second largest adjacency eigenvalue λ 2 (G) of a regular graph. Gu et al. (2016) in [12] presented a more general conjecture on a simple graph G. This conjecture was proved by Liu et al. (2014) in [21] by showing that for any simple graph G with minimum degree δ ≥ 2 k ≥ 4 , if λ 2 (G) < δ − 2 k − 1 δ + 1 , then τ (G) ≥ k. Similar results involving the algebraic connectivity μ n − 1 (G) and the second largest signless Laplacian eigenvalue q 2 (G) of a graph G were also obtained. In this paper, we determine a Moore function f (δ , g) for a graph G with minimum degree δ and girth g , and prove that if G is a simple graph of order n with minimum degree δ ≥ 2 k ≥ 4 and girth g , then (i) If λ 2 (G) < δ − 2 k − 1 f (δ , g) , then τ (G) ≥ k. (ii) If μ n − 1 (G) > 2 k − 1 f (δ , g) , then τ (G) ≥ k. (iii) If q 2 (G) < 2 δ − 2 k − 1 f (δ , g) , then τ (G) ≥ k. The edge-connectivity analogue results are also obtained. Former results in Gu et al. (2016) [12] , Li et al. (2013) [18] , Liu et al. (2014) [20] and Liu et al. (2014) [21] are extended. [ABSTRACT FROM AUTHOR]

Let G be a simple undirected connected graph. Let D (G) be the distance matrix of G and let Tr (G) be the diagonal matrix of the vertex transmissions in G. Let α ∈ [ 0 , 1 ]. In S-Y. Cui et al. (2019) [7] the matrix D α (G) = α Tr (G) + (1 − α) D (G) is introduced and several properties are obtained. In this paper, new properties on the D α -matrix are derived including inequalities that involve the largest vertex transmission and the spectral radii of the distance matrix, distance signless Laplacian matrix and D α -matrix. The necessary and sufficient condition for the equality in each of the inequalities is given. Moreover, some results on the D α -matrix of a graph with independent sets of vertices sharing the same set of neighbors, including the case of a complete multipartite graph, are obtained. Finally, the spectrum of D α (G) is determined when G is the H -join of regular graphs. [ABSTRACT FROM AUTHOR]

For the underlying graph G of a network, k (⩾ 2) spanning trees of G are called completely independent spanning trees (CISTs for short) if they are mutually inner-node-disjoint. It is well-known that determining the existence of k CISTs in a graph is an NP-hard problem, even for k = 2. Also, there exists a k -connected graph which does not possess two CISTs for any k ⩾ 2. Accordingly, researches focused on the problem of constructing multiple CISTs in some particular famous networks. Pai and Chang (2016) proposed a unified approach to recursively construct two CISTs with diameter 2 n − 1 in several n -dimensional hypercube-variant networks for n ⩾ 4 , including locally twisted cubes L T Q n and crossed cubes C Q n. Later on, new constructions showed that the diameter of two CISTs can be reduced to 2 n − 2 if n = 4 and 2 n − 3 if n ⩾ 5 for L T Q n , and to 2 n − 2 if n = 4 , 5 and 2 n − 3 if n ⩾ 6 for C Q n. In this paper, we intend to construct more CISTs for those networks that are paid attention. We develop a novel tree searching algorithm, called two-stages tree-searching algorithm (abbreviated as TS 2), which can be used to construct three CISTs of a 6-regular graph if the scale of the graph is not too large and there exist three CISTs for certain. In particular, we demonstrate that three CISTs of L T Q 6 and C Q 6 can be acquired by using TS 2. Moreover, for high-dimensional L T Q n and C Q n with n ⩾ 7 , we show that their three CISTs can be constructed by recursion. Consequently, we obtain the following results: (i) For L T Q n , the diameters of three CISTs we constructed are 11, 12 and 12 when n = 6 , and all are 2 n − 1 when n ⩾ 7 ; (ii) For C Q n , all diameters of three CISTs we constructed are 12 when n = 6 , and 2 n + 1 when n ⩾ 7. [ABSTRACT FROM AUTHOR]

Motivated by the conjecture of Hartsfield and Ringel on antimagic labellings of undirected graphs, Hefetz, Mütze, and Schwartz initiated the study of antimagic labellings of digraphs in 2010. Very recently, it has been conjectured in Li et al. (2019) that every graph admits an antimagic orientation, which is a strengthening of an earlier conjecture of Hefetz, Mütze and Schwartz. In this paper, we prove that every 2 d -regular graph (not necessarily connected) admits an antimagic orientation, where d ≥ 2. Together with known results, our main result implies that the above-mentioned conjecture is true for all regular graphs. [ABSTRACT FROM AUTHOR]

A l a b e l i n g of a digraph D with m arcs is a bijection from the set of arcs of D to { 1 , 2 , ... , m }. A labeling of D is a n t i m a g i c if no two vertices in D have the same vertex-sum, where the vertex-sum of a vertex u ∈ V (D) for a labeling is the sum of labels of all arcs entering u minus the sum of labels of all arcs leaving u. An orientation D of a graph G is a n t i m a g i c if D has an antimagic labeling. Hefetz et al. (2010) raised the question: Does every graph admit an antimagic orientation? It had been proved that every 2 d -regular graph with at most two odd components has an antimagic orientation. In this paper, we consider 2 d -regular graphs with more than two odd components. We show that every 2 d -regular graph with k (3 ≤ k ≤ 5 d + 4) odd components has an antimagic orientation. And we show that each 2 d -regular graph with k (k ≥ 5 d + 5) odd components admits an antimagic orientation if each odd component has at least 2 x 0 + 5 vertices with x 0 = ⌈ k − (5 d + 4) 2 d − 2 ⌉. [ABSTRACT FROM AUTHOR]

In this paper we investigate bounds on set multipartite Ramsey numbers for the bipartite graph K 2 , n , extending or improving well-known upper bounds by Chung and Graham, Irving, Lortz and Mengersen. Known constructions based on certain classes of combinatorial designs (projective plane, Hadamard matrix, strongly regular graph) yield near-optimal bounds. As the main goal, a new construction based on strongly regular graph and Hadamard matrix produces a sharp class, generalizing a classical bound by Exoo, Harborth, and Mengersen. [ABSTRACT FROM AUTHOR]

Let Γ be a distance-regular graph with valency k and diameter D , and let x be a vertex of Γ . We denote by k i ( 0 ≤ i ≤ D ) the number of vertices at distance i from x . In this paper, we try to quantify the difference between antipodal and non-antipodal distance-regular graphs. We will look at the sum k D − 1 + k D , and consider the situation where k D − 1 + k D ≤ 2 k . If Γ is an antipodal distance-regular graph, then k D − 1 + k D = k D ( k + 1 ) . It follows that either k D = 1 or the graph is non-antipodal. And for a non-antipodal distance-regular graph, it was known that k D ( k D − 1 ) ≥ k and k D − 1 ≥ k both hold. So, this paper concerns on obtaining more detailed information on the number of vertices for a non-antipodal distance-regular graph. We first concentrate on the case where the diameter equals three. In this case, the condition k D + k D − 1 ≤ 2 k is equivalent to the condition that the number of vertices is at most 3 k + 1 . And we extend this result to all diameters. We note that although the result of the diameter 3 case is a corollary of the result of all diameters, the main difficulty is the diameter 3 case, and that the diameter 3 case confirms the following conjecture: there is no primitive distance-regular graph with diameter 3 having the M -property. [ABSTRACT FROM AUTHOR]

A kind of generalization of diagnosability for a network G is g -good-neighbor diagnosability which is denoted by t g (G). Let κ g (G) be the R g -connectivity. Lin et al. (2016) [17] and Xu et al. (2017) [29] gave the same problem independently that: the relationship between the R g -connectivity κ g (G) and t g (G) of a general graph G needs to be studied in the future. In this paper, this open problem is solved for general regular graphs. We firstly establish the relationship of κ g (G) and t g (G) , and obtain that t g (G) = κ g (G) + g under some conditions. Secondly, we obtain the g -good-neighbor diagnosability of data center network D k , n which are t g (D k , n) = (g + 1) (k − 1) + n + g for 1 ≤ g ≤ n − 1 under the PMC model and the MM* model, respectively. Furthermore, we show that D k , n is tightly super (n + k − 1) -connected for n ≥ 2 and k ≥ 2 and we also prove that the largest connected component of the survival graph contains almost all of the remaining vertices in D k , n when n + 2 k − 2 vertices removed. [ABSTRACT FROM AUTHOR]

Let m > n ≥ 2 and g ≥ 4 be positive integers. A graph G is called a bipartite (m , n ; g) -graph if it is a biregular bipartite graph of even girth g with the additional property that all vertices in each of the two partition sets are of the same degree; m in one of them, and n in the other. In analogy with the well-known Cage Problem, if we let v (G) denote the order of G , and let B (m , n ; g) denote the natural lower bound for the order of bipartite (m , n ; g) -graphs obtained as a generalization of the Moore bound for regular graphs, we call the difference v (G) − B (m , n ; g) the excess of G. The focus of this paper is on the study of the question of the existence of bipartite (m , n ; g) -graphs for given parameters (m , n ; g) and excess at most 4. We prove that such graphs are rare by finding restrictive necessary arithmetic conditions on the parameters m , n and g. Furthermore, we prove the non-existence of bipartite (m , n ; g) -graphs of excess at most 4 for all parameters m , n , g where g ≥ 10 and is not divisible by 4, and m > n ≥ 3. In the case when the girth of G is 6, we employ spectral analysis of the distance matrices of G , and find necessary relations between their eigenvalues. Finally, we prove for all pairs m , n , m > n ≥ 3 , that the asymptotic density of the set of even girths g ≥ 8 for which there exists a bipartite (m , n ; g) -graph with excess not exceeding 4 is equal to 0. [ABSTRACT FROM AUTHOR]

Abstract In a network or a graph, the total communicability (TC) has been defined as the sum of the entries in the exponential of the adjacency matrix of the network. This quantity offers a good measure of how easily information spreads across the network, and can be useful in the design of networks having certain desirable properties. In this paper, we obtain some bounds for total communicability of a graph G , T C (G) , in terms of spectral radius of the adjacency matrix, number of vertices, number of edges, minimum degree and the maximum degree of G. Moreover, we find some upper bounds for T C (G) when G is the Cartesian product, tensor product or the strong product of two graphs. In addition, Nordhaus–Gaddum-type results for the total communicability of a graph G are established. [ABSTRACT FROM AUTHOR]

Abstract Let G be a graph of order n. Also let λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n be the eigenvalues of graph G. In this paper, we present the following upper bound on the sum of the k (≤ n) largest eigenvalues of G in terms of the order n and negative inertia θ (the number of negative eigenvalues): ∑ i = 1 k λ i ≤ n 2 (θ + 1) (θ + θ (k θ + k − 1) ) with equality holding if and only if G ≅ n K 1 or G ≅ p K ‾ t (n = p t , p ≥ 2) with k = 1 (where p K ‾ t is the complete p -partite graph of p t vertices with all partition sets having size t). Moreover, we obtain a sharp upper bound on the energy of bipartite graphs with given order n and rank r. We also propose an open problem as follows: Characterize all connected d -regular bipartite graphs of order n with 5 distinct eigenvalues and rank r = 2 n 2 (4 d − n) 2 , where d > n 4. Finally we give a partial solution to this problem. [ABSTRACT FROM AUTHOR]

Abstract A natural generalization of a regular (or equitable) partition of a graph, which makes sense also for non-regular graphs, is the so-called weight-regular partition, which gives to each vertex u ∈ V a weight that equals the corresponding entry ν u of the Perron eigenvector ν . This paper contains three main results related to weight-regular partitions of a graph. The first is a characterization of weight-regular partitions in terms of double stochastic matrices. Inspired by a characterization of regular graphs by Hoffman, we also provide a new characterization of weight-regularity by using a Hoffman-like polynomial. As a corollary, we obtain Hoffman's result for regular graphs. In addition, we show an application of weight-regular partitions to study graphs that attain equality in the classical Hoffman's lower bound for the chromatic number of a graph, and we show that weight-regularity provides a condition under which Hoffman's bound can be improved. [ABSTRACT FROM AUTHOR]

Abstract Highly regular graphs for which not all regularities are explainable by symmetries are fascinating creatures. Some of them like, e.g., the line graph of W. Kantor's non-classical GQ (5 2 , 5) , are stumbling stones for existing implementations of graph isomorphism tests. They appear to be extremely rare and even once constructed it is difficult to prove their high regularity. Yet some of them, like the McLaughlin graph on 275 vertices and Ivanov's graph on 256 vertices are of profound beauty. This alone makes it an attractive goal to strive for their complete classification or, failing this, at least to get a deep understanding of them. Recently, one of the authors discovered new methods for proving high regularity of graphs. Using these techniques, in this paper we study a classical family of strongly regular graphs, originally discovered by A.E. Brouwer, A.V. Ivanov, and M.H. Klin in the late 80s. We analyse their symmetries and show that they are (3 , 5) -regular but not 2-homogeneous. Thus we promote these graphs to the distinguished club of highly regular graphs with few symmetries. [ABSTRACT FROM AUTHOR]

Abstract Fault diagnosis of systems is an important area of study in the design and maintenance of multiprocessor systems. A new measure for fault diagnosis of systems, namely, h -edge tolerable diagnosability, is the maximum number of faulty nodes that a system G can guarantee to locate when the number of faulty links does not exceed h , denoted by t h e (G). Particularly, t 0 e (G) is the traditional diagnosability of G. Chang et al. (2005) [5] determined the traditional diagnosabilities of regular graphs. In this paper, we establish the h -edge tolerable diagnosabilities of regular graphs under the PMC model and the MM⁎ model, which extends their results and provides a more precise characterization for the fault diagnosis capability of regular graphs. As applications, the h -edge tolerable diagnosabilities of many networks are determined under the PMC model and the MM⁎ model. [ABSTRACT FROM AUTHOR]

Let A ( λ , D ) be the adjacency characteristic polynomial of a digraph D . In the paper Deng and Kelmans (2013) the so-called ( x y z ) -transformation D x y z of a simple digraph D was considered, where x , y , z ∈ { 0 , 1 , + , − } , and the formulas of A ( λ , D x y z ) were obtained for every r -regular digraph D in terms of r , the number of vertices of D , and A ( λ , D ) . In this paper we define the so-called ( x y a b ) -transformation D x y a b of a simple digraph D , where x , y , a , b ∈ { 0 , 1 , + , − } . This notion generalizes the previous notion of the ( x y z ) -transformation D x y z , namely, D x y a b = D x y z if and only if a = b = z . We extend our previous results on A ( λ , D x y z ) to the ( x y a b ) -transformation D x y a b by obtaining the formulas of A ( λ , D x y a b ) , where x , y , a , b ∈ { 0 , 1 , + , − } and a ≠ b , for every simple r -regular digraph D in terms of r , the number of vertices of D , and A ( λ , D ) . We also use ( x y a b ) -transformations to describe various constructions providing infinitely many examples of adjacency cospectral non-isomorphic digraphs. [ABSTRACT FROM AUTHOR]

In this paper, we prove a number of related results on distance-regular graphs concerning electric resistance and simple random walk. We begin by proving several results on electric resistance; in particular we prove a sharp constant bounding the ratio of electrical resistances between any two pairs of points and give a counterexample to a conjecture made in a previous paper regarding the growth of resistances with respect to distance. We then show how a number of strong bounds on moments of hitting times, cover times, and related quantities for simple random walk may be deduced from the bound on resistance. [ABSTRACT FROM AUTHOR]

Recently, Davies, Jenssen, Perkins, and Roberts gave a very nice proof of the result (due, in various parts, to Kahn, Galvin–Tetali, and Zhao) that the independence polynomial of a d -regular graph is maximized by disjoint copies of K d , d . Their proof uses linear programming bounds on the distribution of a cleverly chosen random variable. In this paper, we use this method to give lower bounds on the independence polynomial of regular graphs. We also give a new bound on the number of independent sets in triangle-free cubic graphs. [ABSTRACT FROM AUTHOR]

A non-complete distance-regular graph is called geometric if there exists a set C of Delsarte cliques such that each edge lies in exactly one clique in C . Let Γ be a geometric distance-regular graph with diameter D ≥ 3 and smallest eigenvalue θ D . In this paper we show that if Γ contains an induced subgraph K 2 , 1 , 1 , then D ≤ − θ D . Moreover, if − θ D − 1 ≤ D ≤ − θ D then D = − θ D and Γ is a Johnson graph. We also show that for ( s , b ) ⁄ ∈ { ( 11 , 11 ) , ( 21 , 21 ) } , there are no distance-regular graphs with intersection array { 4 s , 3 ( s − 1 ) , s + 1 − b ; 1 , 6 , 4 b } where s , b are integers satisfying s ≥ 3 and 2 ≤ b ≤ s . As an application of these results, we classify geometric distance-regular graphs with D ≥ 3 , θ D ≥ − 4 and containing an induced subgraph K 2 , 1 , 1 . [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph. Denote the Kirchhoff index and the degree-Kirchhoff index of G by K f ( G ) and K f ∗ ( G ) , respectively. This paper considers the asymptotic behavior of K f ( T k ( G ) ) and K f ∗ ( T k ( G ) ) of the iterated total graph T k ( G ) of an r -regular graph G . We show that the asymptotic behavior of these indices is independent of the structure of G and only dependent on the degree and the number of vertices of G . [ABSTRACT FROM AUTHOR]

In this paper, we investigate various algebraic and graph theoretic properties of the distance matrix of a graph. Two graphs are D -cospectral if their distance matrices have the same spectrum. We construct infinite pairs of D -cospectral graphs with different diameter and different Wiener index. A graph is k -transmission-regular if its distance matrix has constant row sum equal to k . We establish tight upper and lower bounds for the row sum of a k -transmission-regular graph in terms of the number of vertices of the graph. Finally, we determine the Wiener index and its complexity for linear k -trees, and obtain a closed form for the Wiener index of block-clique graphs in terms of the Laplacian eigenvalues of the graph. The latter leads to a generalization of a result for trees which was proved independently by Mohar and Merris. [ABSTRACT FROM AUTHOR]

For a distance-regular graph of diameter three Γ, the statement that distance-3 graph Γ 3 of Γ is strongly regular is equivalent to that Γ has eigenvalue −1. There are many distance-regular graphs of diameter 3 having eigenvalue −1, such as the folded 7-cube, generalized hexagons of order ( s , s ) and antipodal nonbipartite distance-regular graphs of diameter 3. In this paper, we show that for a fixed positive integer α ( β , respectively), there are only finitely many distance-regular graphs of diameter 3 having eigenvalue −1 and a 3 = α ( b 1 c 2 = β and a 3 ≠ 0 , respectively). Such distance-regular graphs for small numbers α = 1 , 2 or β = 3 with a 3 ≠ 0 are classified. We show that there are no distance-regular graphs with intersection array { 44 , 35 , 3 ; 1 , 5 , 42 } . Moreover, we classify the distance-regular graphs with diameter 3 and smallest eigenvalue greater than −3. [ABSTRACT FROM AUTHOR]

A sign regular matrix is almost strictly sign regular if all its nontrivial minors of the same order have the same strict sign. These matrices form a subclass of sign regular matrices (matrices whose minors of the same order have the same sign). In this paper, the backward stability for almost strictly sign regular matrices is studied when Neville elimination with two-determinant pivoting strategy is applied. In addition, several numerical experiments are also presented. [ABSTRACT FROM AUTHOR]

This paper considers distributed storage systems (DSSs) from a graph theoretic perspective. A DSS is constructed by means of the path decomposition of a 3 -regular graph into P 4 paths. The paths represent the disks of the DSS and the edges of the graph act as the blocks of storage. We deduce the properties of the DSS from a related graph and show their optimality. [ABSTRACT FROM AUTHOR]

Linear codes with few weights have applications in secret sharing, authentication codes, association schemes, data storage systems, strongly regular graphs and some other fields. Two-weight linear codes are particularly interesting since they are closely related to finite geometry, combinatorial designs, graph theory. In this paper, we present a new approach to constructing linear codes with two or three weights from q -polynomials and study their weight distributions. As an application of two-weight linear codes, we obtain three families of strongly regular graphs. Some of the presented strongly regular graphs are new. [ABSTRACT FROM AUTHOR]

A T -decomposition of a graph G is a set of edge-disjoint copies of T in G that cover the edge set of G . Graham and Häggkvist (1989) conjectured that any 2 ℓ -regular graph G admits a T -decomposition if T is a tree with ℓ edges. Kouider and Lonc (1999) conjectured that, in the special case where T is the path with ℓ edges, G admits a T -decomposition D where every vertex of G is the end-vertex of exactly two paths of D , and proved that this statement holds when G has girth at least ( ℓ + 3 ) ∕ 2 . In this paper we verify Kouider and Lonc’s Conjecture for paths of length 4 . [ABSTRACT FROM AUTHOR]

In this paper we study an elementary functorial construction from the category of finite non-abelian groups to the category of singular compact, oriented 2-manifolds. After a desingularization process this construction results in a finite collection of compact, connected, oriented smooth surfaces equipped with a closed-cell structure which is face and edge transitive. These tessellated surfaces are best viewed as regular or dual quasi-regular maps, i.e., cellular graph embeddings into the surface with a high degree of symmetry. This construction in fact exhibits the noncommutative part of the group's multiplication table as equivalent to a collection of such maps. It generally results in a large collection of maps per group, for example when the construction is applied to Σ 6 it yields 4477 maps of 27 distinct genus. We study the distribution of these maps in various groups. We also show that extensions of groups result in branched coverings between the component surfaces in their decompositions. Finally we exploit functoriality to obtain interesting faithful, orientation preserving actions of subquotients of these groups and their automorphism groups on these surfaces and maps. [ABSTRACT FROM AUTHOR]

Extra connectivity and the pessimistic diagnosis are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processor. The pessimistic diagnosis strategy is a classic strategy based on the PMC model in which isolates all faulty vertices within a set containing at most one fault-free vertex. In this paper, the result that the pessimistic diagnosability t p ( G ) equals the extra connectivity κ 1 ( G ) of a regular graph G under some conditions are shown. Furthermore, the following new results are gotten: the pessimistic diagnosability t p ( S n 2 ) = 4 n − 9 for split-star networks S n 2 ; t p ( Γ n ) = 2 n − 4 for Cayley graphs generated by transposition trees Γ n ; t p ( Γ n ( Δ ) ) = 4 n − 11 for Cayley graph generated by the 2-tree Γ n ( Δ ) ; t p ( B P n ) = 2 n − 2 for the burnt pancake networks B P n . As corollaries, the known results about the extra connectivity and the pessimistic diagnosability of many famous networks including the alternating group graphs, the alternating group networks, BC networks, the k -ary n -cube networks etc. are obtained directly. [ABSTRACT FROM AUTHOR]

In this paper, the orthogonal graph of type ( m , m − 1 , 0 ) over F q of odd characteristic is introduced. We study the elementary properties of the graph and show that the first subconstituent of it is a generalized strongly regular graph. Moreover, the structure of the second subconstituent and the adjacency relations between different subconstituents are given. [ABSTRACT FROM AUTHOR]

In this paper, we study 24 possibilities of directed strongly regular graphs with adjacency matrix of rank 6, our proof is based on two effective algorithms. At last, we get 4 families of directed strongly regular graphs with realizable parameter sets, exclude 20 families of directed strongly regular graphs with feasible parameter sets; partially solve the classification problem of directed strongly regular graphs with adjacency matrix of rank 6. [ABSTRACT FROM AUTHOR]

Let V be an ( n + l ) -dimensional vector space over the finite field F q with l ≥ n > 0 , and W be a fixed l -dimensional subspace of V . Suppose F is a non-trivial intersecting family of n -dimensional subspaces U of V with U ∩ W = 0 . In this paper, we give the tight upper bound for the size of F , and describe the structure of F which reaches the upper bound. [ABSTRACT FROM AUTHOR]

Let Γ denote a bipartite distance-regular graph with diameter D ≥ 4 and valency k ≥ 3 . Let X denote the vertex set of Γ, and let A denote the adjacency matrix of Γ. For x ∈ X let T = T ( x ) denote the subalgebra of Mat X ( C ) generated by A , E 0 ⁎ , E 1 ⁎ , … , E D ⁎ , where for 0 ≤ i ≤ D , E i ⁎ represents the projection onto the i th subconstituent of Γ with respect to x . We refer to T as the Terwilliger algebra of Γ with respect to x . An irreducible T -module W is said to be thin whenever dim E i ⁎ W ≤ 1 for 0 ≤ i ≤ D . By the endpoint of W we mean min { i | E i ⁎ W ≠ 0 } . For 0 ≤ i ≤ D , let Γ i ( z ) denote the set of vertices in X that are distance i from vertex z . Define a parameter Δ 2 in terms of the intersection numbers by Δ 2 = ( k − 2 ) ( c 3 − 1 ) − ( c 2 − 1 ) p 22 2 . In this paper we prove the following are equivalent: (i) Δ 2 > 0 and for 2 ≤ i ≤ D − 2 there exist complex scalars α i , β i with the following property: for all x , y , z ∈ X such that ∂ ( x , y ) = 2 , ∂ ( x , z ) = i , ∂ ( y , z ) = i we have α i + β i | Γ 1 ( x ) ∩ Γ 1 ( y ) ∩ Γ i − 1 ( z ) | = | Γ i − 1 ( x ) ∩ Γ i − 1 ( y ) ∩ Γ 1 ( z ) | ; (ii) For all x ∈ X there exist up to isomorphism exactly two irreducible modules for the Terwilliger algebra T ( x ) with endpoint two, and these modules are thin. [ABSTRACT FROM AUTHOR]

In this paper, we classify antipodal distance-regular graphs of diameter three that admit an arc-transitive action of S U 3 ( q ) . In particular, we find a new infinite family of distance-regular antipodal r -covers of a complete graph on q 3 + 1 vertices, where q is odd and r is any divisor of q + 1 such that ( q + 1 ) ∕ r is odd. Further, we find several new constructions of arc-transitive antipodal distance-regular graphs of diameter three in case λ = μ . [ABSTRACT FROM AUTHOR]

A vertex magic total (VMT) labeling of a graph G = ( V , E ) is a bijection from the set of vertices and edges to the set of integers defined by λ : V ∪ E → { 1 , 2 , … , | V | + | E | } so that for every x ∈ V , w ( x ) = λ ( x ) + ∑ x y ∈ E λ ( x y ) = k , for some integer k . A VMT labeling is said to be a super VMT labeling if the vertices are labeled with the smallest possible integers, 1 , 2 , … , | V | . In this paper we introduce a new method to expand some known VMT labelings of 2-regular graphs. [ABSTRACT FROM AUTHOR]

Let G ( 4 , 2 ) be the set of connected regular graphs with four distinct eigenvalues in which exactly two eigenvalues are simple, G ( 4 , 2 , − 1 ) (resp. G ( 4 , 2 , 0 ) ) the set of graphs belonging to G ( 4 , 2 ) with −1 (resp. 0) as an eigenvalue, and G ( 4 , ≥ − 1 ) the set of connected regular graphs with four distinct eigenvalues and second least eigenvalue not less than −1. In this paper, we prove the non-existence of connected graphs having four distinct eigenvalues in which at least three eigenvalues are simple, and determine all the graphs in G ( 4 , 2 , − 1 ) . As a by-product of this work, we characterize all the graphs belonging to G ( 4 , ≥ − 1 ) and G ( 4 , 2 , 0 ) , respectively, and show that all these graphs are determined by their spectra. [ABSTRACT FROM AUTHOR]

The paper begins with a new characterization of ( k , τ ) -regular sets. Then, using this result as well as the theory of star complements, we derive a simplex-like algorithm for determining whether or not a graph contains a ( 0 , τ ) -regular set. When τ = 1 , this algorithm can be applied to solve the efficient dominating set problem which is known to be NP-complete. If − 1 is not an eigenvalue of the adjacency matrix of the graph, this particular algorithm runs in polynomial time. However, although it does not work in polynomial time in general, we report on its successful application to a vast set of randomly generated graphs. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new construction of directed strongly regular graphs (briefly DSRGs) from smaller ones. With its aid each suitable equitable partition in a single DSRG leads to an infinite family of DSRGs. We construct dozens of infinite families in this way. As a byproduct, we confirm the existence of DSRGs for 29 previously open parameter sets of orders at most 110. [ABSTRACT FROM AUTHOR]