Repository navigation
Folders and files
| Name | Name | Last commit date | ||
|---|---|---|---|---|
Repository files navigation
Edge multiset dimension of subdivided complete graphs ===================================================== Pedro M. M. de Castro, September 23, 2026. Exact finite certificates accompanying the article of the same title. Article (version 3.0): https://doi.org/10.5281/zenodo.22928011 The certificate descriptions and Algorithms 1 and 2 refer to this version of the article, dated September 23, 2026. Files ===== small_matrices.csv contains explicit binary landmark matrices for n=3,...,29. degree_certificates.csv contains degree certificates for n=30,...,9999. This README explains both formats and their exact verification. Use Algorithm 1 in Section 6.4 of the article for the small matrices. Use Algorithm 2 in the same section for the degree certificates. The analytic proof in Appendix A covers all n>=10000. All rows and columns below use zero-based indices. Certificates for the length-three subdivision ============================================= These two CSV files certify the existence of edge multiset resolving sets for every integer n from 3 through 9999. The accompanying article gives an analytic construction for n at least 10000. The graph S_3(K_n) replaces each edge of K_n by a path of three edges. Small matrices: small_matrices.csv ================================== There are 432 data rows describing 27 binary matrices, one for each order n=3,...,29. The header is n,row,c0,...,c28. Both row and column indices start at zero. A record with fields n and row=i specifies row i of an n-by-n matrix M. For j<n, the numeric field c_j is M_ij and must contain exactly 0 or 1. For j>=n, the field must be empty. An empty field is padding outside the matrix; it is not a zero entry. Each pair (n,row) occurs exactly once, and the rows for a given n are exactly 0,...,n-1. The file is arranged by increasing n and row. These two index fields determine the meaning of a record, so reordering records does not change the matrices. A reader must retain the n and row columns and every named matrix column. The complete three-row block for n=3 is: n,row,c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,c21,c22,c23,c24,c25,c26,c27,c28 3,0,0,0,0,,,,,,,,,,,,,,,,,,,,,,,,,, 3,1,0,0,1,,,,,,,,,,,,,,,,,,,,,,,,,, 3,2,1,0,1,,,,,,,,,,,,,,,,,,,,,,,,,, Its matrix is column 0 1 2 row 0 0 0 0 row 1 0 0 1 row 2 1 0 1 All fields c3 through c28 in this block are empty. In particular, M_12=1 and M_21=0: the matrix need not be symmetric. Decode a matrix as a set of graph vertices. Write the replacement path between originals v_i and v_j as v_i - x_ij - x_ji - v_j. A diagonal entry M_ii=1 selects original vertex v_i. An off-diagonal entry M_ij=1 selects x_ij, the internal vertex adjacent to v_i on that path. The n=3 example therefore selects x_12, x_20 and v_2. For a direct check, construct the graph and compute shortest-path distances from every selected vertex using breadth-first search. For each edge uv, initialize six counters H_uv(0),...,H_uv(5). For each selected vertex z, increment the counter at min(distance(z,u),distance(z,v)). All these distances are at most five. The resulting six-entry vectors must be distinct for all graph edges, as checked by Algorithm 1 in the article. Also check that the number of selected vertices is at most n(n-1)/2. This procedure uses the graph itself and applies to each displayed matrix without any hypothesis on its row sums. A reader should reject duplicate or missing (n,row) pairs, row indices outside 0,...,n-1, nonbinary active cells, and nonempty padding cells. The supplied complete file has exactly the orders 3,...,29. Degree certificates: degree_certificates.csv ============================================ There is one record for every n=30,...,9999. The five integer columns are n,p,d,X,Y. These records specify margins and diagonal entries of a realizable binary matrix. Verify that p is prime, p>=n+5, 0<=d<p and X,Y are nonnegative. Put m=(p-1)/2. For i=0,...,n-1, compute r_i = (i(i+3)/2 + d) modulo p, in 0,...,p-1; L_i = (r_i+1) div 2; sigma_i = r_i modulo 2. The operator div is integer division. Sort the indices with sigma_i=1 by the pair (L_i,i). Separately sort the indices with sigma_i=0, after removing index zero. Select the first X indices of the odd class and the first Y indices of the even class. Reject a requested count larger than the corresponding class. The classes are determined by sigma_i before any choices are changed. Put epsilon_i=1 on these selected indices and zero elsewhere. Define Q_i = L_i + epsilon_i (m+1-sigma_i); alpha_i = sigma_i if epsilon_i=0, and alpha_i=1-sigma_i otherwise; q_i = Q_i-alpha_i. Require alpha_0=0, sum_i Q_i=n(n-1)/2 and 0<=q_i<=n-1. For each k=1,...,n, form the n integer weights w_i = i-alpha_i + indicator(q_i>=k). The sum of the k largest weights must be at most sum_i min(q_i,k), for every k. The article proves that these cuts are necessary and sufficient for a binary matrix with row sums i, column sums Q_i and diagonal alpha_i. The identity 2Q_i-alpha_i=r_i+p epsilon_i supplies the additive code used by the resolving construction. The complete file has 9970 records and requires 49994565 cut inequalities. The n field identifies each record, independently of its physical position in the file. Reject missing or repeated orders. All calculations in the verification are exact integer operations. Scope ===== The two files contain existence certificates. The displayed landmark counts need not be minimal. The coverage uses every integer in the stated intervals. It makes no sampling, extrapolation or performance claim. Reuse and citation ================== The data and instructions are licensed under Creative Commons Attribution 4.0 International (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/ When using these certificates, cite Pedro M. M. de Castro, "Edge multiset dimension of subdivided complete graphs", Zenodo, 2026, and identify the article version and repository revision used.