Contributions to Discrete Mathematics (E-Journal, University of Calgary)

Not a member yet

406 research outputs found

Sort by

Lattice paths in corridors and cyclic corridors

Author: Flórez Rigoberto
González Javier
Matijasevick Mateo
Pardo Cristhian
Ramírez José Luis
Simbaqueba Lina
Velandia Fabio
Publication venue: Faculty of Science, University of Calgary
Publication date: 30/04/2024
Field of study

In this paper we use discrete Fourier transform and generating functions to count families of paths of a given length in a corridor. For example, we count Motzkin paths, colored Motzkin paths, Dyck paths, and Schroder paths

Tilings of a honeycomb strip and higher order Fibonacci numbers

Author: Došlić Tomislav
Podrug Luka
Publication venue: Faculty of Science, University of Calgary
Publication date: 30/04/2024
Field of study

In this paper we explore two types of tilings of a honeycomb strip and derive some closed form formulas for the number of tilings. Furthermore, we obtain some new identities involving tribonacci numbers, Padovan numbers and Narayana\u27s cow sequence and provide combinatorial proofs for several known identities about those numbers

Combinatorial proof of Girard-Waring formula

Author: Łukasz Bożyk
Publication venue: Faculty of Science, University of Calgary
Publication date: 30/04/2024
Field of study

\noindent The well-known and celebrated identity of Girard (1629) and Waring (1762) states that

x^n+y^n=\sum_{m=0}^{\lfloor n/2\rfloor}(-1)^m\frac{n}{n-m}\binom{n-m}{m}\left(xy\right)^m\left(x+y\right)^{n-2m}

and can be easily proven algebraically (see H.W. Gould, The Girard--Waring power sum formulas for symmetric functions and Fibonacci sequences,} Fibonacci Quart. 37 (1999), no. 2, 135--140). In this note, we provide a combinatorial proof of this identity

Split lattice paths and Rogers-Ramanujan type identities: Split lattice paths and RR type identities

Author: Marwah Bhanu
Goyal Megha
Publication venue: Faculty of Science, University of Calgary
Publication date: 23/09/2024
Field of study

In this paper, an open problem posed by the second author [On

q

-series and split lattice paths, Graphs and Combinatorics, 2020] is addressed. Here, we provide combinatorial interpretations of four generalized basic series in terms of split lattice paths. Out of these series, two series have been studied by Adiga et. al. [On Generalization of Some Combinatorial Identities, J. Ramanujan Soc. of Math. and Math. Sc., 2016] using split

(n + t)

-color partitions and

R

-weighted lattice paths but a direct one-to-one correspondence between these two classes was missing. We are successful in the quest of establishing bijections between the combinatorial graphical interpretations in terms of split lattice paths and combinatorial interpretations in terms of split

(n + t)

-color partitions using a purely algebraic approach. In this process, we encounter Rogers--Ramanujan type identities and we are able to provide their graphical interpretations using a constructive approach

Prime 2-structures

Author: Ille Pierre
Publication venue: Faculty of Science, University of Calgary
Publication date: 17/04/2024
Field of study

The 2-structures generalize arc-coloured digraphs. They are obtained from a vertex set by considering an equivalence relation between the ordered pairs of distinct vertices. The 2-structures provide a suitable framework to introduce the modular decomposition. A vertex subset of a 2-structure is a module whenever each vertex outside is linked in an equivalent way to all the vertices inside. A 2-structure is prime if it does not admit proper modules with at least 2 elements. Our purpose is to study the possible cardinalities of the prime 2-substructures in a finite or infinite prime 2-structure

Some results about star-factors in graphs

Author: Zhou Sizhong
Xu Yang
Sun Zhiren
Publication venue: Faculty of Science, University of Calgary
Publication date: 23/09/2024
Field of study

For a set

\mathcal{S}

of connected graphs, a subgraph

F

of a graph

G

is defined as an

\mathcal{S}

-factor of

G

F

satisfies that

V(F)=V(G)

and every component of

F

is isomorphic to an element of

\mathcal{S}

. If every component of

F

is a star, then

F

is said to be a star-factor. A star-factor with size at most

n

may be written for a

\{K_{1,t}: 1\leq t\leq n\}

-factor. A graph

G

is called a

\{K_{1,t}: 1\leq t\leq n\}

-factor deleted graph if

G-e

has a

\{K_{1,t}: 1\leq t\leq n\}

-factor for every

e\in E(G)

. The sun toughness of a graph

G

is denoted by

s(G)

and defined as follows :

s(G)=\min \big\{\frac{|X|}{sun(G-X)}: X\subseteq V(G), \ sun(G-X)\geq2 \big\}

G

is not a complete graph, and

s(G)=+\infty

G

is a complete graph, where

sun(G-X)

denotes the number of sun components of

G-X

. In this paper, we prove that (1) if

G

is a connected graph, and its sun toughness satisfies

s(G)\geq\frac{1}{n}

, then

G

admits a

\{K_{1,t}: 1\leq t\leq n\}

-factor; (2) if

G

is a

(k+1)

-connected graph, and its sun toughness s(G)>\frac{k+1}{n+1}, then

G-Y

admits a

\{K_{1,t}: 1\leq t\leq n\}

-factor for any

Y\subseteq V(G)

with

|Y|=k

; (3) if

G

is a 2-edge-connected graph, and its sun toughness

s(G)\geq\frac{1}{n-1}

, then

G

is a

\{K_{1,t}: 1\leq t\leq n\}

-factor deleted graph. Furthermore, it is shown that our results are sharp

Unified framework for tableau models of Grothendieck Polynomials

Author: Hawkes Graham
Publication venue: Faculty of Science, University of Calgary
Publication date: 23/09/2024
Field of study

We give combinatorial proofs of two types of duality for Grothendieck polynomials by constructing a unified combinatorial\\ framework incorporating set-valued tableaux, multiset-valued tableaux, reverse plane partitions and valued-set tableaux. Importantly, our proofs extend to proofs of these dualities for the refined Grothendieck polynomials. The second of these dualities was formerly unknown for the refined case

On characterization and recognition of proper tagged probe interval graphs

Author: Paul Sanchita
Ghosh Shamik
Chakraboty Sourav
Sen Malay
Publication venue: Faculty of Science, University of Calgary
Publication date: 23/09/2024
Field of study

Interval graphs were used in the study of the human genome project by the molecular biologist Benzer. Later on probe interval graphs were introduced by Zhang as a generalization of interval graphs for the study of cosmid contig mapping of DNA. Further research in this area required more useful and cost-effective tools. The concept of tagged probe interval graphs is motivated from this point of view. In this paper, we consider a natural subclass of it, namely, the class of proper tagged probe interval graphs. In this paper, we present a characterization theorem and a linear time recognition algorithm for proper tagged probe interval graphs. Also, we discuss the interrelations between the classes of proper tagged probe interval graphs and tagged probe interval graphs with probe interval graphs and probe proper interval graphs

The Fractional Local Metric Dimension of Graphs

Author: Javaid Imran
Benish Hira
Murtaza Muhammad
Publication venue: Faculty of Science, University of Calgary
Publication date: 23/09/2024
Field of study

The fractional versions of graph-theoretic invariants multiply the range of applications in scheduling, assignment and operational research problems. For this interesting aspect of fractional graph theory, we introduce the fractional version of local metric dimension of graphs. The local resolving neighborhood

L(xy)

of an edge

xy

of a graph

G

is the set of those vertices in

G

which resolve the vertices

x

and

y

. A function

f:V(G)\rightarrow[0, 1]

is a local resolving function of

G

f(L(xy))\geq1

for all edges

xy

G

. The minimum value of

f(V(G))

among all local resolving functions

f

G

is the fractional local metric dimension of

G

. We study the properties and bounds of fractional local metric dimension of graphs and give some characterization results. We determine the fractional local metric dimension of strong and Cartesian product of graphs

Uniformly resolvable ${P_4, C_k}$ -decomposition of $K_n$ - a complete solution

Author: Andiyappan Shanmuga Vadivu
Muthusamy Appu
Publication venue: Faculty of Science, University of Calgary
Publication date: 23/09/2024
Field of study

Let

K_n,

C_{n}

, and

P_{n}

respectively denote the complete graph, cycle and path on

n

vertices. Uniformly resolvable decomposition of

K_n

is a decomposition of

K_n

into subgraphs which can be partitioned into factors containing pairwise isomorphic subgraphs. In this paper, we determine necessary and sufficient conditions for the existence of uniformly resolvable decomposition of

K_n

into

P_4

and $C_k,~ k\geq3.

333

full texts

406

metadata records

Updated in last 30 days.

Contributions to Discrete Mathematics (E-Journal, University of Calgary)

Access Repository Dashboard

Do you manage Open Research Online? Become a CORE Member to access insider analytics, issue reports and manage access to outputs from your repository in the CORE Repository Dashboard! 👇