Stephan Wagner1
1Department of Mathematical Sciences Mathematics Division Stellenbosch University Private Bag X1, Matieland 7602 South Africa
Abstract:

The parity dimension of a graph \( G \) is defined as the dimension of the null space of its closed neighborhood matrix \( N \). A graph with parity dimension \( 0 \) is called all parity realizable (APR). In this paper, a simple recursive procedure for calculating the parity dimension of a tree is given, which is more apt to be used in the context of enumeration than the graph-theoretical characterizations due to Amin, Slater, and Zhang. Applying the recursive relation, we find asymptotic formulas for the number of APR trees and for the average parity dimension of a tree.

Zehui Shao1, Jin Xu1, Lingiang Pan1
1Key Laboratory of Image Processing and Intelligent Control Department of Control Science and Engineering Huazhong University of Science and Technology Wuhan 430074, China
Abstract:

The Ramsey multiplicity \( M(G) \) of a graph \( G \) is defined to be the smallest number of monochromatic copies of \( G \) in any two-coloring of edges of \( K_{R(G)} \), where \( R(G) \) is the smallest integer \( n \) such that every graph on \( n \) vertices either contains \( G \) or its complement contains \( G \). With the help of computer algorithms, we obtain the exact values of Ramsey multiplicities for most of isolate-free graphs on five vertices, and establish upper bounds for a few others.

E-mail Alert

Add your e-mail address to receive upcoming issues of Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC).

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. We actively encourage proposals from our readers and authors, directly submitted to us, encompassing subjects within their respective fields of expertise. The Editorial Team, in conjunction with the Editor-in-Chief, will supervise the appointment of Guest Editors and scrutinize Special Issue proposals to ensure content relevance and appropriateness for the journal. To propose a Special Issue, kindly complete all required information for submission;