Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
A classification of isomorphism-invariant random digraphs
Get PDFWe classify isomorphism-invariant random digraphs \linebreak (IIRDs) according to where randomness lies, namely, on arcs, vertices, vertices and arcs together as arc random digraphs (ARD), vertex random digraphs (VRD), vertex-arc random digraphs (VARD) as an extension of the classification of isomorphism-invariant random graphs (IIRGs) \cite{beer:2011}, and introduce randomness in direction (together with arcs, vertices, etc.) also which in turn yield direction random digraphs (DRDs) and its variants, respectively. We demonstrate that for the number of vertices , ARDs and VRDs are mutually exclusive and are both proper subsets of VARDs, and also demonstrate the existence of VARDs which are neither ARDs nor VRDs, and the existence of IIRDs that are not VARDs (e.g., random nearest neighbor digraphs(RNNDs)). We demonstrate that to obtain a DRD as an IIRD, one has to start with an IIRG and insert directions randomly. Depending on the type of IIRG, we obtain direction-edge random digraphs (DERDs), direction-vertex random digraphs (DVRDs), and direction-vertex-edge random digraphs (DVERDs), and demonstrate that DERDs and DVRDs have an overlap but are mutually exclusive for , and both are proper subsets of DVERDs which is a proper subset of DRDs and also the complement of DRDs in IIRDs is nonempty (e.g., RNNDs). We also study the relation of DRDs with VARDs, VRDs, and ARDs and show that for , the intersection of DERDs and VARDs is ARDs; we provide some results and open problems and conjectures. For example, the relation of DVRDs and DVERDs with the VARDs (hence with ARDs and VRDs) are still open problems for . We also show positive dependence between the arcs of a VARD whose tails are same which implies the asymptotic distribution of the arc density of VRDs and ARDs has nonnegative variance
Nordhaus-Gaddum type inequalities for multiple domination and packing parameters in graphs
Get PDFWe study the Nordhaus-Gaddum type results for and -domination numbers of a graph and investigate these bounds for the -limited packing and -total limited packing numbers in graphs with emphasis on the case . In the special case , we give an upper bound on stronger than the bound presented by Harary and Haynes (1996). Moreover, we establish upper bounds on the sum and product of packing and open packing numbers and characterize all graphs attaining these bounds
An elementary, geometric proof of the non-existence of a projective plane of order 6
Get PDFWe present a fairly elementary, self-contained proof of the nonexistence of a finite projective plane of order . Our approach is motivated by theory of binary codes but does not appeal to it directly
Minimum size blocking sets of certain line sets with respect to an elliptic quadric in
Get PDFFor a given nonempty subset of the line set of \PG(3,q), a set of points of \PG(3,q) is called an -blocking set if each line in contains at least one point of . Consider an elliptic quadric in \PG(3,q). Let (respectively, ) denote the set of all lines of \PG(3,q) which meet in (respectively, ) points. In this paper, we characterize the minimum size -blocking sets in \PG(3,q), where is one of the line sets , , and
Some combinatorial properties of hexagonal lattices
Get PDFIn this paper, we consider the combinatorial properties of the hexagonal lattice. Let be the number of -element order ideals in a hexagonal lattice. We give the enumeration of by showing a bijection between the order ideals and Schröder paths. Further, we get formulae for the flag - and -vectors of the hexagonal lattice
Feedback vertex number of Sierpi\\u27{n}ski-type graphs
Get PDFThe feedback vertex number of a graph is the minimum number of vertices that can be deleted from such that the resultant graph does not contain a cycle. We show that for the Sierpi\\u27{n}ski graph with and . The generalized Sierpi\\u27{n}ski triangle graph is obtained by contracting all non-clique edges from the Sierpi\\u27{n}ski graph . We prove that , and give an upper bound for for the case when
On the illumination of a class of convex bodies
Get PDFWe study Boltyanski’s illumination problem (or Hadwiger\u27s covering problem) for the class of convex bodies in consisting of convex hulls of a pair of compact convex sets contained in two parallel hyperplanes of . This special case of the problem is completely solved when
Hamiltonian-connectedness of triangulations with few separating triangles
Get PDFWe prove that 3-connected plane triangulations containing a single edge contained in all separating triangles are hamiltonian-connected. As a direct corollary we have that 3-connected plane triangulations with at most one separating triangle are hamiltonian-connected. In order to show bounds on the strongest form of this theorem, we proved that for any s >= 4 there are 3-connected triangulation with s separating triangles that are not hamiltonian-connected. We also present computational results which show that all `small\u27 3-connected triangulations with at most 3 separating triangles are hamiltonian-connected
Distinguishing number and distinguishing index of neighbourhood corona of two graphs
Get PDFThe distinguishing number (index) () of a graph is the least integer such that has an vertex labeling (edge labeling) with labels that is preserved only by a trivial automorphism. The neighbourhood corona of two graphs and is denoted by and is the graph obtained by taking one copy of and copies of , and joining the neighbours of the th vertex of to every vertex in the th copy of . In this paper we describe the automorphisms of the graph . Using results on automorphisms, we study the distinguishing number and the distinguishing index of . We obtain upper bounds for and
A wide class of Combinatorial matrices related with Reciprocal Pascal and Super Catalan matrices
Get PDFIn this paper, we present a number of combinatorial matrices that are generalizations or variants of the super Catalan matrix and the reciprocal Pascal matrix. We present explicit formulæ for LU-decompositions of all the matrices and their inverses. To prove the claimed results, we mainly use the celebrated Zeilberger algorithm