Q‐integral unicyclic,bicyclic and tricyclic graphs

A graph is called Q‐integral if its signless Laplacian spectrum consists of integers. In this paper, we characterize a class of k‐cyclic graphs whose second smallest signless Laplacian eigenvalue is less than one. Using this result we determine all the Q‐integral unicyclic, bicyclic and tricyclic graphs.     

First Order Approach and Index Theorems for Discrete and Metric Graphs

The aim of the present paper is to introduce a unified notion of Laplacians on discrete and metric graphs. In order to cover all self-adjoint vertex conditions for the associated metric graph Laplacian, we develop systematically a new type of discrete graph operators acting on a decorated graph. The decoration at each vertex of degree d is given by a subspace of , generalising the fact that a function on the standard vertex space has only a scalar value. We illustrate the abstract concept by giving classical examples throughout the article. Our approach includes infinite graphs as well. We develop the notion of exterior derivative, differential forms, Dirac and Laplace operators in the discrete and metric case, using a supersymmetric framework. We calculate the (supersymmetric) index of the discrete Dirac operator generalising the standard index formula involving the Euler characteristic of a graph. Finally, we show that for finite graphs, the corresponding index for the metric Dirac operator agrees with the discrete one.     

Graphs whose signless Laplacian spectral radius does not exceed the Hoffman limit value

For a graph matrix M, the Hoffman limit value H(M) is the limit (if it exists) of the largest eigenvalue (or, M-index, for short) of M(H_n), where the graph H_n is obtained by attaching a pendant edge to the cycle C_n-1 of length n-1. In spectral graph theory, M is usually either the adjacency matrix A or the Laplacian matrix L or the signless Laplacian matrix Q. The exact values of H(A) and H(L) were first determined by Hoffman and Guo, respectively. Since H_n is bipartite for odd n, we have H(Q)=H(L). All graphs whose A-index is not greater than H(A) were completely described in the literature. In the present paper, we determine all graphs whose Q-index does not exceed H(Q). The results obtained are determinant to describe all graphs whose L-index is not greater then H(L). This is done precisely in Wang et al. (in press) [21].     

On Switching to H‐Free Graphs

In this article, we study the problem of deciding if, for a fixed graph H, a given graph is switching equivalent to an H‐free graph. Polynomial‐time algorithms are known for H having at most three vertices or isomorphic to P₄. We show that for H isomorphic to a claw, the problem is polynomial, too. On the other hand, we give infinitely many graphs H such that the problem is NP‐complete, thus solving an open problem [Kratochvíl, Ne?et?il and Zýka, Ann Discrete Math 51 (1992)]. Further, we give a characterization of graphs switching equivalent to a K_{1, 2}‐free graph by ten forbidden‐induced subgraphs, each having five vertices. We also give the forbidden‐induced subgraphs for graphs switching equivalent to a forest of bounded vertex degrees.     

Eigenvalues of 2-edge-coverings

A 2-edge-covering between G and H is an onto homomorphism from the vertices of G to the vertices of H so that each edge is covered twice and edges in H can be lifted back to edges in G. In this note we show how to compute the spectrum of G by computing the spectrum of two smaller graphs, namely a (modified) form of the covered graph H and another graph which we term the anti-cover. This is done for both the adjacency matrix and the normalized Laplacian. We also give an example of two anti-cover graphs which have the same normalized Laplacian, and state a generalization for directed graphs.     

Connected Q-integral graphs with maximum edge-degree less than or equal to 8

Graphs with integral signless Laplacian spectrum are called Q-integral graphs. The number of adjacent edges to an edge is defined as the edge-degree of that edge. The Q-spectral radius of a graph is the largest eigenvalue of its signless Laplacian. In 2019, Park and Sano [16] studied connected Q-integral graphs with the maximum edge-degree at most six. In this article, we extend their result and study the connected Q-integral graphs with maximum edge-degree less than or equal to eight. Further, we give an upper bound and a lower bound for the maximum edge-degree of a connected Q-integral graph with respect to its Q-spectral radius. As a corollary, we show that the Q-spectral radius of the connected edge-non-regular Q-integral graph with maximum edge-degree five is six, which we anticipate to be a key for solving the unsolved problem of characterizing such graphs.     

The lollipop graph is determined by its Q-spectrum

A graph G is said to be determined by its Q-spectrum if with respect to the signless Laplacian matrix Q, any graph having the same spectrum as G is isomorphic to G. The lollipop graph, denoted by H_n,p, is obtained by appending a cycle C_p to a pendant vertex of a path P_n−p. In this paper, it is proved that all lollipop graphs are determined by their Q-spectra.     

On the extremal values of the second largest Q-eigenvalue

We study extremal graphs for the extremal values of the second largest Q-eigenvalue of a connected graph. We first characterize all simple connected graphs with second largest signless Laplacian eigenvalue at most 3. The second part of the present paper is devoted to the study of the graphs that maximize the second largest Q-eigenvalue. We construct families of such graphs and prove that some of theses families are minimal for the fact that they maximize the second largest signless Laplacian eigenvalue.     

A lowest order divergence-free finite element on rectangular grids

It is shown that the conforming Q _2,1;1,2-Q′₁ mixed element is stable, and provides optimal order of approximation for the Stokes equations on rectangular grids. Here, Q _2,1;1,2 = Q _2,1 × Q _1,2, and Q _2,1 denotes the space of continuous piecewise-polynomials of degree 2 or less in the x direction but of degree 1 in the y direction. Q′₁ is the space of discontinuous bilinear polynomials, with spurious modes filtered. To be precise, Q′₁ is the divergence of the discrete velocity space Q _2,1;1,2. Therefore, the resulting finite element solution for the velocity is divergence-free pointwise, when solving the Stokes equations. This element is the lowest order one in a family of divergence-free element, similar to the families of the Bernardi-Raugel element and the Raviart-Thomas element.     

Scattering on univalent graphs from theL-function point of view

The scattering process on multiloop infinite (p+1)-valent graphs is studied. These graphs are discrete spaces of a constant negative curvature, being quotients of a p-adic hyperbolic plane over free-acting discrete subgroups of the projective group PGL(2,Q _p). They are, in fact, identical to p-adic multiloop surfaces. A finite subgraph containing all loops is called the reduced graph T_red; the L-function is associated with this finite subgraph. For an infinite graph, we introduce the notion of spherical functions. They are eigenfunctions of a discrete Laplace operator acting on the graph. In scattering processes, we define the s-matrix and the scattering amplitudes c_i, imposing the restriction c_i=A_ret(u)/A_adv (u) = const for all vertices u T_supp. A_ret and A_adv are retarded and advanced branches of a solution to the eigenfunction problem and T_supp is a support domain for scattering centers. Taking the product over all c_i, we obtain the determinant of the scattering matrix, which is expressed as a ratio of two L-functions: C L(₊)/L(_–). Here the L-function is the Ihara-Selberg function depending only on the form of T_red, being the eigenvalue of the Laplacian. We present a proof of the Hashimoto-Bass theorem, the expressing L-function L(u) of any finite graph via the determinant of a local operator (u) acting on this graph. Numerous examples of L-function calculations are presented.Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 103, No. 3, pp. 489–506, June, 1995.     

Minimal webs in Riemannian manifolds

For a given combinatorial graph G a geometrization (G, g) of the graph is obtained by considering each edge of the graph as a 1-dimensional manifold with an associated metric g. In this paper we are concerned with minimal isometric immersions of geometrized graphs (G, g) into Riemannian manifolds (N ⁿ , h). Such immersions we call minimal webs. They admit a natural ‘geometric’ extension of the intrinsic combinatorial discrete Laplacian. The geometric Laplacian on minimal webs enjoys standard properties such as the maximum principle and the divergence theorems, which are of instrumental importance for the applications. We apply these properties to show that minimal webs in ambient Riemannian spaces share several analytic and geometric properties with their smooth (minimal submanifold) counterparts in such spaces. In particular we use appropriate versions of the divergence theorems together with the comparison techniques for distance functions in Riemannian geometry and obtain bounds for the first Dirichlet eigenvalues, the exit times and the capacities as well as isoperimetric type inequalities for so-called extrinsic R-webs of minimal webs in ambient Riemannian manifolds with bounded curvature.      

Bounding the Clique‐Width of H‐Free Chordal Graphs

A graph is H‐free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique‐width. Brandstädt, Le, and Mosca erroneously claimed that the gem and co‐gem are the only two 1‐vertex P₄‐extensions H for which the class of H‐free chordal graphs has bounded clique‐width. In fact we prove that bull‐free chordal and co‐chair‐free chordal graphs have clique‐width at most 3 and 4, respectively. In particular, we find four new classes of H‐free chordal graphs of bounded clique‐width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H‐free chordal graphs has bounded clique‐width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of ‐free graphs has bounded clique‐width via a reduction to K₄‐free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique‐width of H‐free weakly chordal graphs.     

On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs

Erdős has conjectured that every subgraph of the n‐cube Q_n having more than (1/2 + o(1))e(Q_n) edges will contain a 4‐cycle. In this note we consider ‘layer’ graphs, namely, subgraphs of the cube spanned by the subsets of sizes k − 1, k and k + 1, where we are thinking of the vertices of Q_n as being the power set of {1,…, n}. Observe that every 4‐cycle in Q_n lies in some layer graph. We investigate the maximum density of 4‐cycle free subgraphs of layer graphs, principally the case k = 2. The questions that arise in this case are equivalent to natural questions in the extremal theory of directed and undirected graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 66–82, 2000     

The divergence theorem and the Laplacian in Minkowski space

Let (X, B) be a Minkowski space (finite-dimensional Banach space) with unit ball B. Using a Minkowski definition of unit normal to a hypersurface, a Minkowski analogue of Euclidean divergence is defined. We show that the divergence theorem holds. Using the Minkowski divergence, a Minkowski Laplacian is defined. We prove that this Laplacian is a second-order, constant-coefficient, elliptic, differential operator. Furthermore, the symbol of this Laplacian is computed and used to associate a natural Euclidean structure with (X, B).Supported, in part, by NSERC Operating Grant #4066.     

On graphs whose Laplacian matrices have distinct integer eigenvalues

In this paper, we investigate graphs for which the corresponding Laplacian matrix has distinct integer eigenvalues. We define the set S_i,n to be the set of all integers from 0 to n, excluding i. If there exists a graph whose Laplacian matrix has this set as its eigenvalues, we say that this set is Laplacian realizable. We investigate the sets S_i,n that are Laplacian realizable, and the structures of the graphs whose Laplacian matrix has such a set as its eigenvalues. We characterize those i < n such that S_i,n is Laplacian realizable, and show that for certain values of i, the set S_i,n is realized by a unique graph. Finally, we conjecture that S_n,n is not Laplacian realizable for n ≥ 2 and show that the conjecture holds for certain values of n. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues

The signless Laplacian matrix of a graph G is defined to be the sum of its adjacency matrix and degree diagonal matrix, and its eigenvalues are called Q-eigenvalues of G. A Q-eigenvalue of a graph G is called a Q-main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. In this work, all trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues are determined.     

Remarks on Q-integral complete multipartite graphs

A graph is Q-integral if the spectrum of its signless Laplacian matrix consists entirely of integers. In their study of Q-integral complete multipartite graphs, [Zhao et al., Q-integral complete r-partite graphs, Linear Algebra Appl. 438 (2013) 1067–1077] posed two questions on the existence of such graphs. We resolve these questions and present some further results characterizing particular classes of Q-integral complete multipartite graphs.     

An expanded mixed covolume method for sobolev equation with convection term on triangular grids

The expanded mixed covolume method for the two‐dimensional Sobolev equation with convection term is developed and studied. This method uses the lowest‐order Raviart‐Thomas mixed finite element space as the trial function space. By introducing a transfer operator γ_h which maps the trial function space into the test function space and combining expanded mixed finite element with mixed covolume method, the continuous‐in‐time, discrete‐in‐time expanded mixed covolume schemes are constructed, and optimal error estimates for these schemes are obtained. Numerical results are given to examine the validity and effectiveness of the proposed schemes.© 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013