Warut Thawinrak1
1Department of Mathematics, University of California, Davis, California USA
Abstract:

The stretched Littlewood-Richardson coefficient ctλ,tμtν was conjectured by King, Tollu, and Toumazet to be a polynomial function in t. It was shown to be true by Derksen and Weyman using semi-invariants of quivers. Later, Rassart used Steinberg’s formula, the hive conditions, and the Kostant partition function to show a stronger result that cλ,μν is indeed a polynomial in variables ν,λ,μ provided they lie in certain polyhedral cones. Motivated by Rassart’s approach, we give a short alternative proof of the polynomiality of ctλ,tμtν using Steinberg’s formula and a simple argument about the chamber complex of the Kostant partition function.

Amrita Acharyya1
1Department of Mathematics and Statistics, University of Toledo, Ohio 43606, USA
Abstract:

In this work, we study type B set partitions for a given specific positive integer k defined over n={n,(n1),,1,0,1,,n1,n}. We found a few generating functions of type B analogues for some of the set partition statistics defined by Wachs, White and Steingrímsson for partitions over positive integers [n]={1,2,,n}, both for standard and ordered set partitions respectively. We extended the idea of restricted growth functions utilized by Wachs and White for set partitions over [n], in the scenario of n and called the analogue as Signed Restricted Growth Function (SRGF). We discussed analogues of major index for type B partitions in terms of SRGF. We found an analogue of Foata bijection and reduced matrix for type B set partitions as done by Sagan for set partitions of [n] with specific number of blocks k. We conclude with some open questions regarding the type B analogue of some well known results already done in case of set partitions of [n].

Danjun Huang1, Jiayan Wang1, Weifan Wang1, Puning Jing2
1Department of Mathematics, Zhejiang Normal University, Jinhua 321004, China
2Department of School of Mathematical and Statistics, Xuzhou University of technology, Xuzhou 221018, China
Abstract:

Suppose that ϕ is a proper edge-k-coloring of the graph G. For a vertex vV(G), let Cϕ(v) denote the set of colors assigned to the edges incident with v. The proper edge-k-coloring ϕ of G is strict neighbor-distinguishing if for any adjacent vertices u and v, Cϕ(u)Cϕ(v) and Cϕ(v)Cϕ(u). The strict neighbor-distinguishing index, denoted χsnd(G), is the minimum integer k such that G has a strict neighbor-distinguishing edge-k-coloring. In this paper we prove that if G is a simple graph with maximum degree five, then χsnd(G)12.

Italo Dejter1
1Department of Mathematics, University of Puerto Rico. Rio Piedras, PR 00936-8377
Abstract:

Let 2kZ. A total coloring of a k-regular simple graph via k+1 colors is an efficient total coloring if each color yields an efficient dominating set, where the efficient domination condition applies to the restriction of each color class to the vertex set. In this work, focus is set upon graphs of girth k+1. Efficient total colorings of finite connected simple cubic graphs of girth 4 are constructed starting at the 3-cube. It is conjectured that all of them are obtained by means of four basic operations. In contrast, the Robertson 19-vertex (4,5)-cage, the alternate union Petk of a (Hamilton) 10k-cycle with k pentagon and k-pentagram 5-cycles, for k>1 not divisible by 5, and its double cover Dodk, contain TCs that are nonefficient. Applications to partitions into 3-paths and 3-stars are given.

Jocelyn Minini1, Micha Wasem2
1School of Engineering and Architecture, HES-SO University of Applied Sciences and Arts Western Switzerland, P\’erolles 80, 1700 Fribourg, Switzerland
2Faculty of Mathematics and Computer Science, UniDistance Suisse, Schinerstrasse 18, 3900 Brig, Switzerland
Abstract:

Using generating functions, we are proposing a unified approach to produce explicit formulas, which count the number of nodes in Smolyak grids based on various univariate quadrature or interpolation rules. Our approach yields, for instance, a new formula for the cardinality of a Smolyak grid, which is based on Chebyshev nodes of the first kind and it allows to recover certain counting-formulas previously found by Bungartz-Griebel, Kaarnioja, Müller-Gronbach, Novak-Ritter and Ullrich.

Shibsankar Das1, Virendra Kumar1
1Department of Mathematics, Institute of Science, Banaras Hindu University, Varanasi 221005, Uttar Pradesh, India
Abstract:

Topological indices have become an essential tool to investigate theoretical and practical problems in various scientific areas. In chemical graph theory, a significant research work, which is associated with the topological indices, is to deduce the ideal bounds and relationships between known topological indices. Mathematical development of the novel topological index is valid only if the topological index shows a good correlation with the physico-chemical properties of chemical compounds. In this article, the chemical applicability of the novel GQ and QG indices is calibrated over physico-chemical properties of 22 benzenoid hydrocarbons. The GQ and QG indices predict the physico-chemical properties of benzenoid hydrocarbons, significantly. Additionally, this work establishes some mathematical relationships between each of the GQ and QG indices and each of the graph invariants: size, degree sequences, maximum and minimum degrees, and some well-known degree-based topological indices of the graph.

Paola T. Pantoja1, Rodrigo Chimelli1, Simone Dantas1, Rodrigo Marinho2, Daniel F.D. Posner3
1 IME, Universidade Federal Fluminense, Niterói, RJ, 24210-201, Brazil
2CS-CAC, Federal University of Santa Maria, Cachoeira do Sul, RS, 96503-205, Brazil
3CC-IM, Federal Rural University of Rio de Janeiro, Nova Iguaçu, RJ, 26020-740, Brazil
Abstract:

In 2003, the frequency assignment problem in a cellular network motivated Even et al. to introduce a new coloring problem: Conflict-Free coloring. Inspired by this problem and by the Gardner-Bodlaender’s coloring game, in 2020, Chimelli and Dantas introduced the Conflict-Free Closed Neighborhood k-coloring game (CFCN k-coloring game). The game starts with an uncolored graph G, k2 different colors, and two players, Alice and Bob, who alternately color the vertices of G. Both players can start the game and respect the following legal coloring rule: for every vertex v, if the closed neighborhood N[v] of v is fully colored then there exists a color that was used only once in N[v]. Alice wins if she ends up with a Conflict-Free Closed Neighborhood k-coloring of G, otherwise, Bob wins if he prevents it from happening. In this paper, we introduce the game for open neighborhoods, the Conflict-Free Open Neighborhood k-coloring game (CFON k-coloring game), and study both games on graph classes determining the least number of colors needed for Alice to win the game.

Shude Long1, Junliang Cai2
1Department of Mathematics, Chongqing University of Arts and Sciences, Chongqing, 402160, P.R.China
2School of Mathematical Sciences, Beijing Normal University, Beijing 100875, P.R.China
Abstract:

This paper investigates the number of rooted biloopless nonseparable planar near-triangulations and presents some formulae for such maps with three parameters: the valency of root-face, the number of edges and the number of inner faces. All of them are almost summation-free.

Wei-Ping Ni1, Wen-yao Song1
1School of Mathematics and Statistics, Zaozhuang University, Shandong, 277160, China
Abstract:

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, we confirm the total-coloring conjecture for 1-planar graphs without 4-cycles with maximum degree Δ10.

Gee-Choon Lau1, Wai Chee Shiu2
177D, Jalan Suboh, 85000 Segamat, Johor, Malaysia
2Department of Mathematics, The Chinese University of Hong Kong, Shatin, Hong Kong, P.R. China
Abstract:

For a graph G=(V,E) of size q, a bijection f:E{1,2,,q} is a local antimagic labeling if it induces a vertex labeling f+:VN such that f+(u)f+(v), where f+(u) is the sum of all the incident edge label(s) of u, for every edge uvE(G). In this paper, we make use of matrices of fixed sizes to construct several families of infinitely many tripartite graphs with local antimagic chromatic number 3.

S. Nazari-Moghaddam1, M. Chellali2, S.M. Sheikholeslami3
1Department of Mathematics University of Ilam Ilam, Iran
2LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
3Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran
Abstract:

An outer independent double Roman dominating function (OIDRDF) of a graph G is a function f:V(G){0,1,2,3} satisfying the following conditions:
(i) every vertex v with f(v)=0 is adjacent to a vertex assigned 3 or at least two vertices assigned 2;
(ii) every vertex v with f(v)=1 has a neighbor assigned 2 or 3;
(iii) no two vertices assigned 0 are adjacent.
The weight of an OIDRDF is the sum of its function values over all vertices, and the outer independent double Roman domination number γoidR(G) is the minimum weight of an OIDRDF on G. Ahangar et al. [Appl. Math. Comput. 364 (2020) 124617] established that for every tree T of order n4, γoidR(T)54n and posed the question of whether this bound holds for all connected graphs. In this paper, we show that for a unicyclic graph G of order n, γoidR(G)5n+24, and for a bicyclic graph, γoidR(G)5n+44. We further characterize the graphs attaining these bounds, providing a negative answer to the question posed by Ahangar et al.

R. Ponraj1, K. Annathurai2, R. Kala3
1Department of Mathematics, Sri Paramakalyani College, Alwarkurichi-627 412, India
2Department of Mathematics, Thiruvalluvar College, Papanasam–627 425, India
3Department of Mathematics, Manonmaniam Sundaranar University, Tirunelveli-627012, India
Abstract:

Let G be a (p,q) graph. Let f be a function from V(G) to the set {1,2,,k} where k is an integer 2<k|V(G)|. For each edge uv assign the label r where r is the remainder when f(u) is divided by f(v) (or) f(v) is divided by f(u) according as f(u)f(v) or f(v)f(u). f is called a k-remainder cordial labeling of G if |vf(i)vf(j)|1, i,j{1,,k} where vf(x) denote the number of vertices labeled with x and |ηe(0)ηo(1)|1 where ηe(0) and ηo(1) respectively denote the number of edges labeled with even integers and number of edges labeled with odd integers. A graph with admits a k-remainder cordial labeling is called a k-remainder cordial graph. In this paper we investigate the 4-remainder cordial labeling behavior of Prism, Crossed prism graph, Web graph, Triangular snake, LnmK1, Durer graph, Dragon graph.

Mingqiang An1, Runli Tian2, Huiya Yan3
1College of Science, Tianjin University of Science and Technology, Tianjin, 300457, P.R. China
2School of Software Engineering, Changsha Institute of Technology, Changsha, 410200, P.R. China
3Mathematics and Statistics Department, University of Wisconsin-La Crosse, La Crosse, WI 54601, USA
Abstract:

Given a connected graph H, its first Zagreb index M1(H) is equal to the sum of squares of the degrees of all vertices in H. In this paper, we give a best possible lower bound on M1(H) that guarantees H is τ-path-coverable and τ-edge-Hamiltonian, respectively. Our research supplies a continuation of the results presented by Feng et al. (2017).

A. Anu1, S. Monikandan2
1Department of Mathematics, Vivekananda College, Agasteeswaram, Kanyakumari, Tamilnadu, India
2Department of Mathematics, Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli, Tamilnadu, India
Abstract:

The degree of an edge uv of a graph G is dG(u)+dG(v)2. The degree associated edge reconstruction number of a graph G (or dern(G)) is the minimum number of degree associated edge-deleted subgraphs that uniquely determines G. Graphs whose vertices all have one of two possible degrees d and d+1 are called (d,d+1)-bidegreed graphs. It was proved, in a sequence of two papers [1,17], that dern(mK1,3)=4 for m>1, dern(mK2,3)=dern(rP3)=3 for m>0, r>1 and dern(G)=1 or 2 for all other bidegreed graphs G except the (d,d+1)-bidegreed graphs in which a vertex of degree d+1 is adjacent to at least two vertices of degree d. In this paper, we prove that dern(G)=1 or 2 for this exceptional bidegreed graphs G. Thus, dern(G)4 for all bidegreed graphs G.

Xiaoya Li1, Wenyao Song2, Lianying Miao1
1School of Mathematics, China University of Mining and Technology, Xuzhou, 221116, P. R. China
2School of Mathematics and Statistics, Zaozhuang University, Zaozhuang, 277160, P. R. China
Abstract:

A proper total coloring of a graph G such that there are at least 4 colors on those vertices and edges incident with a cycle of G, is called an acyclic total coloring. The acyclic total chromatic number of G, denoted by χa(G), is the smallest number of colors such that G has an acyclic total coloring. In this article, we prove that for any graph G with Δ(G)=Δ which satisfies χ(G)A for some constant A, and for any integer r, 1r2Δ, there exists a constant c>0 such that if g(G)cΔrlogΔ2r, then χa(G)A+r.

E-mail Alert

Add your e-mail address to receive upcoming issues of Ars Combinatoria.

Call for papers

Special issue: Proceedings of International Conference on Discrete Mathematics (ICDM 2025)

Guest editors: Peter J Cameron, Ambat Vijayakumar, Aparna Lakshmanan S

Special Issues

The Combinatorial Press Editorial Office routinely extends invitations to scholars for the guest editing of Special Issues, focusing on topics of interest to the scientific community.