SCL 2.3 - STAR COMPLEMENT LIBRARY ================================= Corrected release: 17 July 2026 1. PURPOSE ---------- SCL implements the star-complement extension algorithm for signed graphs. For a signed graph H and a prescribed real number lambda that is not an eigenvalue of H, the program: 1. determines the admissible {0,1,-1}-vectors; 2. removes the vectors that produce the redundant twin types prescribed for lambda in {0,1,-1}; 3. constructs the compatibility graph, retaining isolated compatibility vertices; 4. determines its maximal cliques; 5. constructs the associated maximal basic extensions; and 6. removes switching-isomorphic duplicates arising from the fixed input H. The program accompanies the paper Characterization of signed graphs with rank at most four using star complements. 2. CORRECTIONS INCLUDED IN THIS RELEASE --------------------------------------- This corrected release retains the version number 2.3 because it replaces, rather than extends, the previous implementation. It includes the following corrections: - isolated vertices of the compatibility graph are retained; - redundant candidate vectors are removed before clique construction; - for lambda = 0, candidates producing twins are removed; - for lambda = 1, candidates producing (-)-twins are removed; - for lambda = -1, candidates producing (+)-twins are removed; - when there are no non-redundant candidates, the empty set is returned as the unique maximal clique and the initial graph H is returned as the associated self-extended case; and - switching isomorphism is checked by degree-preserving permutations followed by propagation of the required switching signs. For lambda = 1, if a candidate vertex is compared with a vertex of H, the candidate is removed when either (edge = -1 and the external rows are equal), or (edge = 1 and the external rows are opposite). For lambda = -1, it is removed when either (edge = 1 and the external rows are equal), or (edge = -1 and the external rows are opposite). 3. REQUIREMENTS --------------- - Python 3; - NumPy. NumPy can be installed, if necessary, by running python -m pip install numpy On Windows, the command may instead begin with "py": py -m pip install numpy No compilation is required. The program is a Python script. 4. PROGRAM FILE AND WORKING DIRECTORY ------------------------------------- The program file is scl.py Place scl.py and the input file input.txt in the same directory. The generated files are written to that directory. Existing files with the same names are overwritten, so a separate directory should be used for every input whose output is to be preserved. 5. INPUT FORMAT --------------- The file input.txt contains the adjacency matrix of H, followed by a line specifying lambda. The adjacency matrix must be symmetric, have zero diagonal, and have all off-diagonal entries in {0,1,-1}. The lambda line must begin with the word "lambda" and have the form lambda = value For example, the input for P_3 and lambda = 1 is 0 1 0 1 0 1 0 1 0 lambda = 1 The prescribed value must not be an eigenvalue of H. If it is, the program reports this fact and does not compute extensions. 6. RUNNING THE PROGRAM ---------------------- Open a terminal or command prompt in the directory containing scl.py and input.txt, and run python scl.py On Windows, one may use py scl.py 7. GENERATED FILES ------------------ The program generates the following files: bvectors.txt The admissible vectors remaining after redundancy filtering. The vectors b and -b represent switching-equivalent choices, so only one is retained. compatibility_graph.txt The adjacency matrix of the compatibility graph. Its vertices correspond to the vectors in bvectors.txt, in the same order. Isolated compatibility vertices are included. mextensions.txt All raw extensions obtained from the maximal cliques of the compatibility graph. If the empty clique is maximal, this file contains the initial graph H itself. output.txt The extensions remaining after switching-isomorphism reduction among the outputs obtained from the fixed input H. The spectrum printed after each matrix is a numerical aid and is not used as a substitute for the adjacency matrix. 8. INTERPRETATION OF THE OUTPUT COUNTS -------------------------------------- The number of matrices in mextensions.txt is the number of raw maximal-clique outputs for the particular input H. The number in output.txt is the number of switching non-isomorphic outputs for that same input. SCL does not automatically perform a global switching-isomorphism reduction between extensions obtained from different star complements. Consequently, when several star complements are processed, the sum of the numbers in their output.txt files need not equal the number of global switching classes. 9. NUMERICAL TOLERANCE ---------------------- The default numerical tolerance is 1e-6. Eigenvalues printed in the output are rounded to ten decimal places. Candidate quadratic forms, eigenvalue multiplicities, spectra used as an isomorphism prefilter, and the final matrix comparison are tested with the stated tolerance. For the validation checks listed below, the accepted vectors, ranks, and characteristic polynomials were additionally checked using exact integer or rational arithmetic. 10. VALIDATION CHECKS --------------------- The following checks were performed for the corrected release. (a) Self-extended case For K_2 and lambda = 0, the two initially admissible vectors are removed by the twin test. The compatibility graph has no vertices, its unique maximal clique is empty, and the program returns K_2 itself. (b) P_3 and lambda = 1 The program finds five candidates before redundancy filtering and retains exactly two. Both are isolated compatibility vertices. They give two raw one-vertex extensions, which reduce to one switching class, namely H_1. (c) Positive K_3 and lambda = 1 The program finds six candidates before redundancy filtering and retains exactly three. They give three raw one-vertex extensions, which reduce to the same switching class H_1. (d) The case lambda = -1 The runs for -P_3 and negative K_3 retain respectively two and three non-redundant candidates and give the negations of the corresponding outputs for lambda = 1. 11. PUBLIC LOCATION AND SUGGESTED CITATION ------------------------------------------ Public location: https://poincare.matf.bg.ac.rs/~zstanic/scl/scl.py Suggested citation: Z. Stanić, SCL - Star Complement Library, version 2.3, corrected release of 17 July 2026, available at https://poincare.matf.bg.ac.rs/~zstanic/scl/scl.py.