On some subclasses of well-covered graphs

A set of points in a graph is independent if no two points in the set are adjacent. A graph is well covered if every maximal independent set is a maximum independent set or, equivalently, if every independent set is contained in a maximum independent set. The well-covered graphs are classified by the W_n property: For a positive integer n, a graph G belongs to class W_n if ≥ n and any n disjoint independent sets are contained in n disjoint maximum independent sets. Constructions are presented that show how to build infinite families of W_n graphs containing arbitrarily large independent sets. A characterization of W_n graphs in terms of well-covered subgraphs is given, as well as bounds for the size of a maximum independent set and the minimum and maximum degrees of points in W_n graphs.     

Adjacency preservers,symmetric matrices,and cores

It is shown that the graph Γ _n that has the set of all n×n symmetric matrices over a finite field as the vertex set, with two matrices being adjacent if and only if the rank of their difference equals one, is a core if n≥3. Eigenvalues of the graph Γ _n are calculated as well.     

Independent perfect domination sets in Cayley graphs

In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube Q_n has an independent perfect domination set if and only if Q_n is a regular covering of the complete graph K_n+1 if and only if n = 2^m ? 1 for some natural number m. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 213–219, 2001     

Symmetric edge-decompositions of hypercubes

We call a set of edgesE of the n-cubeQ _n a fundamental set for Q _n if for some subgroupG of the automorphism group ofQ _n , theG-translates ofE partition the edge set ofQ _n .Q _n possesses an abundance of fundamental sets. For example, a corollary of one of our main results is that if |E| =n and the subgraph induced byE is connected, then if no three edges ofE are mutually parallel,E is a fundamental set forQ _n . The subgroupG is constructed explicitly. A connected graph onn edges can be embedded intoQ _n so that the image of its edges forms such a fundamental set if and only if each of its edges belongs to at most one cycle.We also establish a necessary condition forE to be a fundamental set. This involves a number-theoretic condition on the integersa _j (E), where for 1 j n, a _j (E) is the number of edges ofE in thej ^th direction (i.e. parallel to thej ^th coordinate axis).     

Fully invariant transformations and associated groups

It is well known that the symmetric group S _ntogether with one idempotent of rank n- 1 on a finite n-element set Nserves as a set of generators for the semigroup T _nof all the total transformations on N. It is also well known that the singular part Sing _n of T _n can be generated by a set of idempotents of rank n- 1. The purpose of this paper is to begin an investigation of the way in which Sing_nand its subsemigroups can be generated by the conjugates of a subset of elements of T _n by a subgroup of S _n . We look for the smallest subset of elements of T _n that will serve and, correspondingly, for a characterization of those subgroups of S _n that will serve. Using some techniques from graph theory we prove our main result:the conjugates of a single transformation of rank n- 1 under Gsuffice to generate Sing_nif and only if Gis what we define to be a 2-block transitive subgroup of S _n .     

Bounds on a generalized domination parameter

Abstract

If n is an integer, n ≥ 2 and u and v are vertices of a graph G, then u and v are said to be K_n-adjacent vertices of G if there is a subgraph of G, isomorphic to K_n , containing u and v. For n ≥ 2, a K_n- dominating set of G is a set D of vertices such that every vertex of G belongs to D or is K_n-adjacent to a vertex of D. The K_n-domination number γK_n (G) of G is the minimum cardinality among the K_n-dominating sets of vertices of G. It is shown that, for n ε {3,4}, if G is a graph of order p with no K_n-isolated vertex, then γK_n (G) ≤ p/n. We establish that this is a best possible upper bound. It is shown that the result is not true for n ≥ 5.     

Cycle‐minors and subdivisions of wheels

In this paper we prove two results. The first is an extension of a result of Dirac which says that any set of n vertices of an n‐connected graph lies in a cycle. We prove that if V′ is a set of at most 2n vertices in an n‐connected graph G, then G has, as a minor, a cycle using all of the vertices of V′. The second result says that if G is an n+1‐connected graph with maximum vertex degree Δ then G contains a subgraph that is a subdivision of W_2n if and only if Δ≥2n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 100–108, 2009     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

ON ARC-TRANSITIVE CIRCULANT DIGRAPHS

Denote by c,(s)the circulant digraph with vertex set zn=[0,1,2……n-1]and symbol set s(≠-s)∈zn\[0].let x be the automorphism group of cn(S)and xo the stabilizer of o in x.then cn(S)is arctransitive if and only if xo acts transitively on s.in this paper,co(S)with xo is being the symmetric group is characterized by its symbot set .by the way all the arctransitive clcculant digraphs of degree 2are given.     

The norm theorem for quadratic forms over a field of characteristic 2

ABSTRACT

In this paper we prove that a finite group G is isomorphic to the finite simple group L _n (q) with n ≥ 3 if and only if they have the same set of order of solvable subgroups.

     

Minimal Blocking Sets in PG(n, 2) and Covering Groups by Subgroups

In this article we prove that a set of points B of PG(n, 2) is a minimal blocking set if and only if ?B? = PG(d, 2) with d odd and B is a set of d + 2 points of PG(d, 2) no d + 1 of them in the same hyperplane. As a corollary to the latter result we show that if G is a finite 2-group and n is a positive integer, then G admits a ? _n+1-cover if and only if n is even and G? (C ₂) ⁿ , where by a ? _m -cover for a group H we mean a set 𝒞 of size m of maximal subgroups of H whose set-theoretic union is the whole H and no proper subset of 𝒞 has the latter property and the intersection of the maximal subgroups is core-free. Also for all n < 10 we find all pairs (m,p) (m > 0 an integer and p a prime number) for which there is a blocking set B of size n in PG(m,p) such that ?B? = PG(m,p).     

ISOMORPHISMS OF CIRCULANT DIAGAPHS

ＩＳＯＭＯＲＰＨＩＳＭＳＯＦＣＩＲＣＵＬＡＮＴＤＩＡＧＡＰＨＳＭＥＮＧＪＩＸＩＡＮＧＡＮＤＨＵＡＮＧＱＩＯＮＧＸＩＡＮＧＡｂｓｔｒａｃｔ：ＬｅｔＳＺｎ－｛０｝．ＴｈｅｃｉｒｃｕｌａｎｔｄｉｇｒａｐｈＤＣｎ（Ｓ）ｉｓａｄｉｒｅｃｔｅｄｇｒａｐｈｗｉｔｈ...     

Multipartite Ramsey numbers for odd cycles

In this paper we study multipartite Ramsey numbers for odd cycles. We formulate the following conjecture: Let n≥5 be an arbitrary positive odd integer; then, in any two‐coloring of the edges of the complete 5‐partite graph K((n?1)/2, (n?1)/2, (n?1)/2, (n?1)/2, 1) there is a monochromatic C_n, a cycle of length n. This roughly says that the Ramsey number for C_n (i.e. 2n?1 ) will not change (somewhat surprisingly) if four large “holes” are allowed. Note that this would be best possible as the statement is not true if we delete from K_2n?1 the edges within a set of size (n+ 1)/2. We prove an approximate version of the above conjecture. © 2009 Wiley Periodicals, Inc. J Graph Theory 61:12‐21, 2009     

Maps on spaces of symmetric matrices preserving idempotence

Suppose F is an arbitrary field. Let |F| be the number of the elements of F. Let M_n(F) be the space of all n×n matrices over F, and let S_n(F) be the subset of M_n(F) consisting of all symmetric matrices. Let V{S_n(F),M_n(F)}, a map Φ:V→V is said to preserve idempotence if A-λB is idempotent if and only if Φ(A)-λΦ(B) is idempotent for any A,BV and λF. It is shown that: when the characteristic of F is not 2, |F|>3 and n4, Φ:S_n(F)→S_n(F) is a map preserving idempotence if and only if there exists an invertible matrix PM_n(F) such that Φ(A)=PAP^-1 for every AS_n(F) and P^tP=aI_n for some nonzero scalar a in F.     

Perpendicular Rectangular Latin Arrays

A set {A ₁, A ₂,..., A _t } of rectangular arrays, each defined on a symbol set X, is said to be t-perpendicular if each t-element subset of X occurs precisely once when the arrays are superimposed. We investigate the existence of sets of r by s rectangular arrays which are row-Latin, column-Latin and t-perpendicular. For example, we show that for all odd n, there exists a pair of row- and column-Latin 2-perpendicular r by s arrays with symbol set X of size n if and only if and r, s ≤ n.     

ANEW RELATION-COMBINING THEOREM AND ITS APPLICATION

Let ?ⁿ denote the set of all formulas ?x₁…?x_n[P(x₁, …,x_n) = 0], where P is a polynomial with integer coefficients. We prove a new relation-combining theorem from which it follows that if ?ⁿ is undecidable over N, then ?²ⁿ⁺² is undecidable over Z.     

Packing,covering and decomposing of a complete uniform hypergraph into delta-systems

Anh-uniform hypergraph generated by a set of edges {E ₁,...,E _c} is said to be a delta-system Δ(p,h,c) if there is ap-element setF such that ∇F|=p andE _i⌢E _j=F,∀i≠j. The main result of this paper says that givenp, h andc, there isn ₀ such that forn≥n ₀ the set of edges of a completeh-uniform hypergraphK _n ^h can be partitioned into subsets generating isomorphic delta-systems Δ(p, h, c) if and only if . This result is derived from a more general theorem in which the maximum number of delta-systems Δ(p, h, c) that can be packed intoK _n ^h and the minimum number of delta-systems Δ(p, h, c) that can cover the edges ofK _n ^h are determined for largen. Moreover, we prove a theorem on partitioning of the edge set ofK _n ^h into subsets generating small but not necessarily isomorphic delta-systems.     

Dominating sets in n-cubes

A perfectdominatingset S of a graph Γ is a set of vertices of Γ such that every vertex of Γ is either in S or is adjacent to exactly one vertex of S. We show that a perfect dominating set of the n-cube Q_n induces a subgraph of Q_n whose components are isomorphic to hypercubes. We conjecture that each of these hypercubes has the same dimension. We then prove that if Q_r is a component of the subgraph induced by S, then n ? r ? 1 or 3 (mod 6). A number of examples are given and connections with Steiner Systems and codes are noted.     

On the smallest limited snake of unit disks

A limited snake of size n is a set of nonoverlapping unit disks D ₁, ..., D _nwith centers c ₁, ..., c _nwhere the distances ¦c _i c _j¦=2 if and only if ¦i–j¦=1, and no disk can touch D ₁ or D _nwithout further common points with D ₁, ..., D _nThe size of the smallest limited snake is proved to be 10.     

Sequences with equi-distributed extreme points in uniform polynomial approximation

Let E be a compact set in with connected complement and positive logarithmic capacity. For any f continuous on E and analytic in the interior of E, we consider the distribution of extreme points of the error of best uniform polynomial approximation on E. Let Λ=(n_j) be a subsequence of such that n_j+1/n_j→1. If, for nΛ, A_n( f)∂E denotes the set of extreme points of the error function, we prove that there is a subsequence Λ′ of Λ such that the distribution of any (n+2)th Fekete point set of A_n( f) tends weakly to the equilibrium distribution on E as n→∞ in Λ′. Furthermore, we prove a discrepancy result for the distribution of the point sets if the boundary of E is smooth enough.