Intersecting antichains and shadows in linear lattices

We establish a homomorphism of finite linear lattices onto the Boolean lattices via a group acting on linear lattices. By using this homomorphism we prove the intersecting antichains in finite linear lattices satisfy an LYM-type inequality, as conjectured by Erd?s, Faigle and Kern, and we state a Kruskal-Katona type theorem for the linear lattices.     

Bernstein type theorem of minimal Lagrangian graphs in quaternion Euclidean space H^n

In this paper, a Bernstein type theorem for minimal Lagrangian submanifolds in quaternion Euclidean space Hn is studied.     

Bernstein type theorem of minimal Lagrangian graphs in quaternion Euclidean space H n

In this paper, a Bernstein type theorem for minimal Lagrangian submanifolds in quaternion Euclidean space H^n is studied.     

Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight

A graph H is defined to be light in a family H of graphs if there exists a finite number φ(H,H) such that each G∈H which contains H as a subgraph, contains also a subgraph K≅H such that the Δ_G(K)≤φ(H,H). We study light graphs in families of polyhedral graphs with prescribed minimum vertex degree δ, minimum face degree ρ, minimum edge weight w and dual edge weight w^∗. For those families, we show that there exists a variety of small light cycles; on the other hand, we also present particular constructions showing that, for certain families, the spectrum of short cycles contains irregularly scattered cycles that are not light.     

Note on unicyclic graphs with given number of pendent vertices and minimal energy

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let G(n,p) denote the set of unicyclic graphs with n vertices and p pendent vertices. In [H. Hua, M. Wang, Unicyclic graphs with given number of pendent vertices and minimal energy, Linear Algebra Appl. 426 (2007) 478-489], Hua and Wang discussed the graphs that have minimal energy in G(n,p), and determined the minimal-energy graphs among almost all different cases of n and p. In their work, certain case of the values was left as an open problem in which the minimal-energy species have to be chosen in two candidate graphs, but cannot be determined by comparing of the corresponding coefficients of their characteristic polynomials. This paper aims at solving the problem completely, by using the well-known Coulson integral formula.     

Heavy fans, cycles and paths in weighted graphs of large connectivity

A set of paths joining a vertex y and a vertex set L is called (y,L)-fan if any two of the paths have only y in common, and its width is the number of paths forming it. In weighted graphs, it is known that the existence of heavy fan is useful to find a heavy cycle containing some specified vertices.In this paper, we show the existence of heavy fans with large width containing some specified vertices in weighted graphs of large connectivity, which is a weighted analogue of Perfect's theorem. Using this, in 3-connected weighted graphs, we can find heavy cycles containing three specified vertices, and also heavy paths joining two specified vertices containing two more specified vertices. These results extend the previous results in 2-connected weighted graphs to 3-connected weighted graphs.     

Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs

Given an undirected multigraph G=(V,E), a family W of sets W⊆V of vertices (areas), and a requirement function r:W→Z⁺ (where Z⁺ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least r(W) edge-disjoint paths between v and W for every pair of a vertex v∈V and an area W∈W. So far this problem was shown to be NP-hard in the uniform case of r(W)=1 for each W∈W, and polynomially solvable in the uniform case of r(W)=r?2 for each W∈W. In this paper, we show that the problem can be solved in time, even if r(W)?2 holds for each W∈W, where n=|V|, m=|{{u,v}|(u,v)∈E}|, p=|W|, and r^*=max{r(W)∣W∈W}.     

Connected signed graphs of fixed order,size, and number of negative edges with maximal index

In this paper we focus on connected signed graphs of fixed number of vertices, positive edges and negative edges that maximize the largest eigenvalue (also called the index) of their adjacency matrix. In the first step we determine these signed graphs in the set of signed generalized theta graphs. Concerning the general case, we use the eigenvector techniques for getting some structural properties of resulting signed graphs. In particular, we prove that positive edges induce nested split subgraphs, while negative edges induce double nested signed subgraphs. We observe that our concept can be applied when considering balancedness of signed graphs (the property that is extensively studied in both mathematical and non-mathematical context).     

Association schemes from the action of PGL(2, q) fixing a nonsingular conic in PG(2, q)

The group PGL(2,q) has an embedding into PGL(3,q) such that it acts as the group fixing a nonsingular conic in PG(2,q). This action affords a coherent configuration (q) on the set (q) of non-tangent lines of the conic. We show that the relations can be described by using the cross-ratio. Our results imply that the restrictions ₊(q) and ₋(q) of (q) to the set ₊(q) of secant (hyperbolic) lines and to the set ₋(q) of exterior (elliptic) lines, respectively, are both association schemes; moreover, we show that the elliptic scheme ₋(q) is pseudocyclic.We further show that the coherent configurations (q ²) with q even allow certain fusions. These provide a 4-class fusion of the hyperbolic scheme ₊(q ²), and 3-class fusions and 2-class fusions (strongly regular graphs) of both schemes ₊(q ²) and ₋(q ²). The fusion results for the hyperbolic case are known, but our approach here as well as our results in the elliptic case are new.     

Gauss-Bonnet Formula, Finiteness Condition, and Characterizations of Graphs Embedded in Surfaces

Let G be an infinite graph embedded in a closed 2-manifold, such that each open face of the embedding is homeomorphic to an open disk and is bounded by finite number of edges. For each vertex x of G, define the combinatorial curvature

Theorems of Erd?s-Ko-Rado type in polar spaces

We consider Erd?s-Ko-Rado sets of generators in classical finite polar spaces. These are sets of generators that all intersect non-trivially. We characterize the Erd?s-Ko-Rado sets of generators of maximum size in all polar spaces, except for H(4n+1,q²) with n?2.     

A characterization of Q-polynomial distance-regular graphs

Let Γ denote a distance-regular graph with diameter D3. Let θ denote a nontrivial eigenvalue of Γ and let denote the corresponding dual eigenvalue sequence. In this paper we prove that Γ is Q-polynomial with respect to θ if and only if the following (i)–(iii) hold:

(i) There exist such that

(1)

(ii) There exist such that the intersection numbers a_i satisfy

for 0iD, where and are the scalars which satisfy Eq. (1) for i=0, i=D, respectively.

(iii) for 1iD.

A class of amply regular graphs related to the subconstituents of a dual polar graph

The connected components of the induced graphs on each subconstituent of the dual polar graph of the odd dimensional orthogonal spaces over a finite field are shown to be amply regular. The connected components of the graphs on the second and third subconstituents are shown to be distance-regular by elementary methods.     

Metric dimension of symplectic dual polar graphs and symmetric bilinear forms graphs

In this paper, by constructing resolving sets of symplectic dual polar graphs and symmetric bilinear forms graphs, we obtain upper bounds on their metric dimension.     

Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs

We prove the nonexistence of a distance-regular graph with intersection array {74,54,15;1,9,60} and of distance-regular graphs with intersection arrays

{4r³+8r²+6r+1,2r(r+1)(2r+1),2r²+2r+1;1,2r(r+1),(2r+1)(2r²+2r+1)}