Search results for "Discrete Mathematics and Combinatorics"
showing 10 items of 230 documents
Maximum weight relaxed cliques and Russian Doll Search revisited
2015
Trukhanov et al. [Trukhanov S, Balasubramaniam C, Balasundaram B, Butenko S (2013) Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations. Comp. Opt. and Appl., 56(1), 113–130] used the Russian Doll Search (RDS) principle to effectively find maximum hereditary structures in graphs. Prominent examples of such hereditary structures are cliques and some clique relaxations intensely discussed and studied in network analysis. The effectiveness of the tailored RDS by Trukhanov et al. for s-plex and s-defective clique can be attributed to their cleverly designed incremental verification procedures used to distinguish feasible from infeasible struct…
Über den Rang der projektiven Darstellung von Kettengeometrien auf Grassmann-Mannigfaltigkeiten
1985
An optimal bound for embedding linear spaces into projective planes
1988
Abstract Linear spaces with υ >n 2 − 1 2 n + 1 points, b⩽n2 + n + 1 lines and not constant point degree are classified. It turns out that there is essentially one class of such linear spaces which are not near pencils and which can not be embedded into any projective plane of order n.
Cyclic and lift closures for k…21-avoiding permutations
2011
We prove that the cyclic closure of the permutation class avoiding the pattern k(k-1)...21 is finitely based. The minimal length of a minimal permutation is 2k-1 and these basis permutations are enumerated by (2k-1).c"k where c"k is the kth Catalan number. We also define lift operations and give similar results. Finally, we consider the toric closure of a class and we propose some open problems.
Extremum degree sets of irregular oriented graphs and pseudodigraphs
2006
The irregularity strength of circulant graphs
2005
AbstractThe irregularity strength of a simple graph is the smallest integer k for which there exists a weighting of the edges with positive integers at most k such that all the weighted degrees of the vertices are distinct. In this paper we study the irregularity strength of circulant graphs of degree 4. We find the exact value of the strength for a large family of circulant graphs.
Remarks on Partially Square Graphs, Hamiltonicity and Circumference
2001
The equidistribution of some Mahonian statistics over permutations avoiding a pattern of length three
2022
Abstract We prove the equidistribution of several multistatistics over some classes of permutations avoiding a 3-length pattern. We deduce the equidistribution, on the one hand of inv and foz e ″ statistics, and on the other hand that of maj and makl statistics, over these classes of pattern avoiding permutations. Here inv and maj are the celebrated Mahonian statistics, foz e ″ is one of the statistics defined in terms of generalized patterns in the 2000 pioneering paper of Babson and Steingrimsson, and makl is one of the statistics defined by Clarke, Steingrimsson and Zeng in (1997) [5] . These results solve several conjectures posed by Amini in (2018) [1] .
On extremal intersection numbers of a block design
1982
K.N. Majumdar has shown that for a 2-(v, k, @l) design D there are three numbers @a, @t, and @S such that each intersection number of D is not greater than @S and not less than max{@a, @t}. In this paper we investigate designs having one of these 'extremal' intersection numbers. Quasisymmetric designs with at least one extremal intersection number are characterized. Furthermore, we show that a smooth design D having the intersection number @S or @a>0 is isomorphic to the system of points and hyperplanes of a finite projective space. Using this theorem, we can characterize all smooth strongly resolvable designs.