Title: Valid path-based graph vertex numbering Show Chinese title

Title: 有效的基于路径的图顶点编号

Abstract: A labelling of a graph is an assignment of labels to its vertex or edge sets (or both), subject to certain conditions, a well established concept. A labelling of a graph G of order n is termed a numbering when the set of integers {1,...,n} is used to label the vertices of G distinctly. A 2-path (a path with three vertices) in a vertex-numbered graph is said to be valid if the number of its middle vertex is smaller than the numbers of its endpoints. The problem of finding a vertex numbering of a given graph that optimises the number of induced valid 2-paths is studied, which is conjectured to be in the NP-hard class. The reported results for several graph classes show that apparently there are not one or more numbering patterns applicable to different classes of graphs, which requires the development of a specific numbering for each graph class under study. Show Chinese abstract

Abstract: 图的标记是将标签分配给其顶点或边集（或两者）的过程，这是一个已确立的概念。一个阶数为n的图G的标记称为编号，当使用整数集合{1,...,n}来唯一地标记G的顶点时。在顶点编号图中，一个2路径（三个顶点的路径）被认为是有效的，如果其中间顶点的编号小于其端点的编号。研究了找到给定图的顶点编号以优化诱导的有效2路径数量的问题，该问题被推测属于NP难类。对于几种图类的报告结果表明，显然不存在一种或多种适用于不同图类的编号模式，这需要为正在研究的每个图类开发特定的编号。