Strongly regular graphs constructed from <Emphasis Type="Italic">p</Emphasis>-ary bent functions

In this paper, we generalize the construction of strongly regular graphs in Tan et al. (J. Comb. Theory, Ser. A 117:668–682, 2010) from ternary bent functions to p-ary bent functions, where p is an odd prime. We obtain strongly regular graphs with three types of parameters. Using certain non-quadratic p-ary bent functions, our constructions can give rise to new strongly regular graphs for small parameters.     

On a conjecture of Brouwer involving the connectivity of strongly regular graphs

In this paper, we study a conjecture of Andries E. Brouwer from 1996 regarding the minimum number of vertices of a strongly regular graph whose removal disconnects the graph into non-singleton components.We show that strongly regular graphs constructed from copolar spaces and from the more general spaces called Δ-spaces are counterexamples to Brouwer?s Conjecture. Using J.I. Hall?s characterization of finite reduced copolar spaces, we find that the triangular graphs T(m), the symplectic graphs Sp(2r,q) over the field Fq (for any q prime power), and the strongly regular graphs constructed from the hyperbolic quadrics O⁺(2r,2) and from the elliptic quadrics O⁻(2r,2) over the field F₂, respectively, are counterexamples to Brouwer?s Conjecture. For each of these graphs, we determine precisely the minimum number of vertices whose removal disconnects the graph into non-singleton components. While we are not aware of an analogue of Hall?s characterization theorem for Δ-spaces, we show that complements of the point graphs of certain finite generalized quadrangles are point graphs of Δ-spaces and thus, yield other counterexamples to Brouwer?s Conjecture.We prove that Brouwer?s Conjecture is true for many families of strongly regular graphs including the conference graphs, the generalized quadrangles GQ(q,q) graphs, the lattice graphs, the Latin square graphs, the strongly regular graphs with smallest eigenvalue −2 (except the triangular graphs) and the primitive strongly regular graphs with at most 30 vertices except for few cases.We leave as an open problem determining the best general lower bound for the minimum size of a disconnecting set of vertices of a strongly regular graph, whose removal disconnects the graph into non-singleton components.     

Intriguing Sets of Points of Q(2n, 2) \Q +(2n ? 1, 2)

Intriguing sets of vertices have been studied for several classes of strongly regular graphs. In the present paper, we study intriguing sets for the graphs Γ _n , n ≥ 2, which are defined as follows. Suppose Q(2n, 2), n?≥ 2, is a nonsingular parabolic quadric of PG(2n, 2) and Q ⁺(2n ? 1, 2) is a nonsingular hyperbolic quadric obtained by intersecting Q(2n, 2) with a suitable nontangent hyperplane. Then the collinearity relation of Q(2n, 2) defines a strongly regular graph Γ _n on the set Q(2n, 2) \ Q ⁺(2n ? 1, 2). We describe some classes of intriguing sets of Γ _n and classify all intriguing sets of Γ₂ and Γ₃.     

ON CLASSES OF REGULAR GRAPHS WITH CONSTANT METRIC DIMENSION

In this paper,we are dealing with the study of the metric dimension of some classes of regular graphs by considering a class of bridgeless cubic graphs called the flower snarks Jn,a class of cubic convex polytopes considering the open problem raised in [M.Imran et al.,families of plane graphs with constant metric dimension,Utilitas Math.,in press] and finally Harary graphs H 5,n by partially answering to an open problem proposed in [I.Javaid et al.,Families of regular graphs with constant metric dimension,Utilitas Math.,2012,88:43-57].We prove that these classes of regular graphs have constant metric dimension.     

p-Ary and q-ary versions of certain results about bent functions and resilient functions

Using the Teichmüller character and Gauss sums, we obtain the following results concerning p-ary bent functions and q-ary resilient functions: (1) a characterization of certain q-ary resilient functions in terms of their coefficients; (2) stronger upper bounds for the degree of p-ary bent functions; (3) determination of all bent functions on ; (4) a characterization of ternary weakly regular bent functions in terms of their coefficients.     

Distance-balanced graphs: Symmetry conditions

A graph X is said to be distance-balanced if for any edge uv of X, the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. A graph X is said to be strongly distance-balanced if for any edge uv of X and any integer k, the number of vertices at distance k from u and at distance k+1 from v is equal to the number of vertices at distance k+1 from u and at distance k from v. Exploring the connection between symmetry properties of graphs and the metric property of being (strongly) distance-balanced is the main theme of this article. That a vertex-transitive graph is necessarily strongly distance-balanced and thus also distance-balanced is an easy observation. With only a slight relaxation of the transitivity condition, the situation changes drastically: there are infinite families of semisymmetric graphs (that is, graphs which are edge-transitive, but not vertex-transitive) which are distance-balanced, but there are also infinite families of semisymmetric graphs which are not distance-balanced. Results on the distance-balanced property in product graphs prove helpful in obtaining these constructions. Finally, a complete classification of strongly distance-balanced graphs is given for the following infinite families of generalized Petersen graphs: GP(n,2), GP(5k+1,k), GP(3k±3,k), and GP(2k+2,k).     

Strongly regular Cayley graphs from partitions of subdifference sets of the Singer difference sets

In this paper, we give a new lifting construction of “hyperbolic” type of strongly regular Cayley graphs. Also we give new constructions of strongly regular Cayley graphs over the additive groups of finite fields based on partitions of subdifference sets of the Singer difference sets. Our results unify some recent constructions of strongly regular Cayley graphs related to m-ovoids and i-tight sets in finite geometry. Furthermore, some of the strongly regular Cayley graphs obtained in this paper are new or nonisomorphic to known strongly regular graphs with the same parameters.     

A construction of bent functions from plateaued functions

In this presentation, a technique for constructing bent functions from plateaued functions is introduced and analyzed. This generalizes earlier techniques for constructing bent from near-bent functions. Using this construction, we obtain a big variety of inequivalent bent functions, some weakly regular and some non-weakly regular. Classes of bent functions having some additional properties that enable the construction of strongly regular graphs are formed, and explicit expressions for bent functions with maximal degree are presented.     

A link between combinatorial designs and three-weight linear codes

In this paper, we show that partial geometric designs can be constructed from certain three-weight linear codes, almost bent functions and ternary weakly regular bent functions. In particular, we show that existence of a family of partial geometric difference sets is equivalent to existence of a certain family of three-weight linear codes. We also provide a link between ternary weakly regular bent functions, three-weight linear codes and partial geometric difference sets.     

Constructing few-weight linear codes and strongly regular graphs

Linear codes with few weights have applications in data storage systems, secret sharing schemes, graph theory and so on. In this paper, we construct a class of few-weight linear codes by choosing defining sets from cyclotomic classes and we also establish few-weight linear codes by employing weakly regular bent functions. Notably, we get some codes that are minimal and we also obtain a class of two-weight optimal punctured codes with respect to the Griesmer bound. Finally, we get a class of strongly regular graphs with new parameters by using the obtained two-weight linear codes.     

Strongly regular graphs and finite Ramsey theory

Some connections between strongly regular graphs and finite Ramsey theory are drawn. Let B_n denote the graph K₂+K?_n. If there exists a strongly regular graph with parameters (υ, k, λ, μ), then the Ramsey number r(B_λ+1, B_{υ?2k+μ ?1})?υ+1. We consider the implications of this inequality for both Ramsey theory and the theory of strongly regular graphs.     

Polynomial addition sets and polynomial digraphs

Let G be a group of order v, and f(x) be a nonzero integral polynomial. A (v, k, f(x))-polynomial addition set in G is a subset D of G with k distinct elements such that f(Σ_d∈Dd) = λΣ_g∈Gg for some integer λ. We discuss some general properties of polynomial addition sets. The relation between polynomial addition sets and polynomial Cayley digraphs is studied and, in particular, some new results on Cayley xⁿ-digraphs and strongly regular Cayley graphs are obtained. Finally, a complete list of polynomial addition sets with certain restrictions on parameters is given.     

A Classification of the Strongly Regular Generalised Johnson Graphs

The generalised Johnson graphs are the graphs J(n, k, m) whose vertices are the k subsets of {1, 2, . . . , n}, with two vertices J ₁ and J ₂ joined by an edge if and only if ${{|J_1 \cap J_2| = m}}$ . A graph is called d-regular if every vertex has exactly d edges incident to it. A d-regular graph on v vertices is called a (v, d, a, c)-strongly regular graph if every pair of adjacent vertices have exactly a common neighbours and every pair of non-adjacent vertices have exactly c common neighbours. The triangular graphs J(n, 2, 1), their complements J(n, 2, 0), the sporadic examples J(10, 3, 1) and J(7, 3, 1), as well as the trivially strongly regular graphs J(2k, k, 0) are examples of strongly regular generalised Johnson graphs. In this paper we prove that there are no other strongly regular generalised Johnson graphs.     

The maximum cut problem on blow-ups of multiprojective spaces

The maximum cut problem for a quintic del Pezzo surface Bl₄(?²) asks: Among all partitions of the 10 exceptional curves into two disjoint sets, what is the largest possible number of pairwise intersections? In this article we show that the answer is 12. More generally, we obtain bounds for the maximum cut problem for the minuscule varieties X _a,b,c :=Bl _b+c ((? ^c?1) ^a?1) studied by Mukai and Castravet-Tevelev and show that these bounds are asymptotically sharp for infinite families and exact in some cases. The key to our results is the fact that certain natural embeddings of the classes of (?1)-divisors on these varieties are optimal for the semidefinite relaxation of the maximum cut problem on graphs proposed by Goemans and Williamson. These results are a new optimality property of Weyl orbits of root systems of type A,D and E. Motivated by our results on the varieties X _a,b,c we show that the Goemans–Williamson maxcut stochastic approximation algorithm has provably optimal asymptotic performance in symmetric strongly regular graphs of bounded spectra, in marked contrast with its worst-case behavior.     

Binary Codes of Strongly Regular Graphs

For strongly regular graphs ith adjacency matrix A, we look at the binary codes generated by A and A + I. We determine these codes for some families of graphs, e pay attention to the relation beteen the codes of switching equivalent graphs and, ith the exception of two parameter sets, we generate by computer the codes of all knon strongly regular graphs on fewer than 45 vertices.     

The spectra of some families of digraphs

Let G be a digraph (or a graph, when seen as a symmetric digraph) with adjacency matrix A, having the eigenvalue λ with associated eigenvector v. As it is well known, the entries of v can be interpreted as charges in each vertex. Then, the linear transformation v ? Av corresponds to a natural displacement of charges, where each vertex sends a copy of its charge to its in-neighbors and absorbs a copy of the charges of its out-neighbors, so the resulting charge distribution is just λv. In this work we use this approach to derive some old and new results about the spectral characterization of G. More precisely, we show how to obtain the spectra of some families of (di)graphs, such as the partial line digraphs and the line graphs of regular or semiregular graphs.     

Efficient algorithms for decomposing graphs under degree constraints

Stiebitz [Decomposing graphs under degree constraints, J. Graph Theory 23 (1996) 321-324] proved that if every vertex v in a graph G has degree d(v)?a(v)+b(v)+1 (where a and b are arbitrarily given nonnegative integer-valued functions) then G has a nontrivial vertex partition (A,B) such that d_A(v)?a(v) for every v∈A and d_B(v)?b(v) for every v∈B. Kaneko [On decomposition of triangle-free graphs under degree constraints, J. Graph Theory 27 (1998) 7-9] and Diwan [Decomposing graphs with girth at least five under degree constraints, J. Graph Theory 33 (2000) 237-239] strengthened this result, proving that it suffices to assume d(v)?a+b (a,b?1) or just d(v)?a+b-1 (a,b?2) if G contains no cycles shorter than 4 or 5, respectively.The original proofs contain nonconstructive steps. In this paper we give polynomial-time algorithms that find such partitions. Constructive generalizations for k-partitions are also presented.     

Linear codes with few weights from weakly regular plateaued functions

Linear codes with few nonzero weights have wide applications in secret sharing, authentication codes, association schemes and strongly regular graphs. Recently, Wu et al. (2020) obtained some few-weighted linear codes by employing bent functions. In this paper, inspired by Wu et al. and some pioneers' ideas, we use a kind of functions, namely, general weakly regular plateaued functions, to define the defining sets of linear codes. Then, by utilizing some cyclotomic techniques, we construct some linear codes with few weights and obtain their weight distributions. Notably, some of the obtained codes are almost optimal with respect to the Griesmer bound. Finally, we observe that our newly constructed codes are minimal for almost all cases.     

Characterization of the odd graphs Ok by parameters

In this note, we settle a problem of N. Biggs [4, p.80] by showing that for each k, no distance regular graph non-isomorphic to the odd graph O_k can have the same parameters as O_k. A related characterization of certain graphs associated with the Johnson scheme J(2k+1, k) is also given.     

Constructing and classifying neighborhood anti-Sperner graphs

For a simple graph G let N_G(u) be the (open) neighborhood of vertex u∈V(G). Then G is neighborhood anti-Sperner (NAS) if for every u there is a v∈V(G)?{u} with N_G(u)⊆N_G(v). And a graph H is neighborhood distinct (ND) if every neighborhood is distinct, i.e., if N_H(u)≠N_H(v) when u≠v, for all u and v∈V(H).In Porter and Yucas [T.D. Porter, J.L. Yucas. Graphs whose vertex-neighborhoods are anti-sperner, Bulletin of the Institute of Combinatorics and its Applications 44 (2005) 69-77] a characterization of regular NAS graphs was given: ‘each regular NAS graph can be obtained from a host graph by replacing vertices by null graphs of appropriate sizes, and then joining these null graphs in a prescribed manner’. We extend this characterization to all NAS graphs, and give algorithms to construct all NAS graphs from host ND graphs. Then we find and classify all connected r-regular NAS graphs for r=0,1,…,6.