On the packing number of $ 3 $-token graph of the path graph $ P_n $
Copyright policy )On the packing number of $ 3 $-token graph of the path graph $ P_n $
<abstract><p>In 2018, J. M. Gómez et al. showed that the problem of finding the packing number $ \rho(F_2(P_n)) $ of the 2-token graph $ F_2(P_n) $ of the path $ P_n $ of length $ n\ge 2 $ is equivalent to determining the maximum size of a binary code $ S' $ of constant weight $ w = 2 $ that can correct a single adjacent transposition. By determining the exact value of $ \rho(F_2(P_n)) $, they proved a conjecture of Rob Pratt. In this paper, we study a related problem, which consists of determining the packing number $ \rho(F_3(P_n)) $ of the graph $ F_3(P_n) $. This problem corresponds to the Sloane's problem of finding the maximum size of $ S' $ of constant weight $ w = 3 $ that can correct a single adjacent transposition. Since the maximum packing set problem is computationally equivalent to the maximum independent set problem, which is an NP-hard problem, then no polynomial time algorithms are expected to be found. Nevertheless, we compute the exact value of $ \rho(F_3(P_n)) $ for $ n\leq 12 $, and we also present some algorithms that produce a lower bound for $ \rho(F_3(P_n)) $ with $ 13\leq n\leq 44 $. Finally, we establish an upper bound for $ \rho(F_3(P_n)) $ with $ n\geq 13 $.</p></abstract>
Computer Networks and Communications, Constraint Satisfaction Problems, algorithms, Graph, Optical Code Division Multiple Access, Engineering, error correcting codes, QA1-939, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Electrical and Electronic Engineering, packing number, Computer network, Butterfly graph, Line graph, binary codes, Voltage graph, Path (computing), Discrete mathematics, 3-token graphs, Computer science, Networks on Chip in System-on-Chip Design, Computational Theory and Mathematics, Security token, Combinatorics, Computer Science, Physical Sciences, Windmill graph, Mathematics, Graph Theory and Algorithms
Computer Networks and Communications, Constraint Satisfaction Problems, algorithms, Graph, Optical Code Division Multiple Access, Engineering, error correcting codes, QA1-939, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Electrical and Electronic Engineering, packing number, Computer network, Butterfly graph, Line graph, binary codes, Voltage graph, Path (computing), Discrete mathematics, 3-token graphs, Computer science, Networks on Chip in System-on-Chip Design, Computational Theory and Mathematics, Security token, Combinatorics, Computer Science, Physical Sciences, Windmill graph, Mathematics, Graph Theory and Algorithms
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!