A POLYNOMIAL ALGORITHM FOR FINDING THE MINIMUM FEEDBACK VERTEX SET OF A 3-REGULAR SIMPLE GRAPH 1

A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.     

一个求外平面图最小顶点赋权反馈点集的线性时间算法

若从一个图中去掉某些顶点后得到的导出子图是无圈图,则所去的那些顶点组成的集合就是原图的反馈点集.本文主要考虑外平面图中的反馈点集并给出了一个求外平面图最小顶点赋权反馈点集的线性时间算法.     

A POLYNOMIAL ALGORITHM FOR FINDING THE MINIMUM FEEDBACK VERTEX SET OF A 3-REGULAR SIMPLE GRAPH

1IntroductionLetG=(VE)beaconnectedsimplegraph.AsubsetFofvertexsetViscalIedafeedbackvertexsetofGifthegraPhGFisaf0rest.ThecardinaIity0faminimumfeedbackvertexset0fGisdenotedbyf(G).AvertexsubsetJofvertexsetViscaJledallonseparatingindependentsetofG,ifJisanilldependentsetofVandGJisconnected.Thema-xiammcardinalityofnollseparatingindependelltsetofGisden0tedbyz(G)andiscalledthenonseparatingindepelldentnumberofG,AgraphGiscalledacactusifGisc0nnectedandanytwocyclesofGaredisjoint.Avertexvofacon…     

A POLYNOMIAL ALGORITHM FOR FINDING THE MINIMUM FEEDBACKVERTEX SET OF A 3-REGULAR SIMPLE GRAPHR1

A subset of the vertex set of a graph is a feedback vertex set of thegraph if the resulting graph is a forest after removed the vertexsubset from the graph. A polynomial algorithm for finding a minimumfeedback vertex set of a 3-regular simple graph is provided.     

Total domination changing and stable graphs upon vertex removal

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. A graph is total domination vertex removal stable if the removal of an arbitrary vertex leaves the total domination number unchanged. On the other hand, a graph is total domination vertex removal changing if the removal of an arbitrary vertex changes the total domination number. In this paper, we study total domination vertex removal changing and stable graphs.     

Partitioning the Vertices of a Graph into Two Total Dominating Sets

A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex of S. We study graphs whose vertex set can be partitioned into two total dominating sets. In particular, we develop several sufficient conditions for a graph to have a vertex partition into two total dominating sets. We also show that with the exception of the cycle on five vertices, every selfcomplementary graph with minimum degree at least two has such a partition.     

Graphs with disjoint dominating and paired-dominating sets

A dominating set of a graph is a set of vertices such that every vertex not in the set is adjacent to a vertex in the set, while a paired-dominating set of a graph is a dominating set such that the subgraph induced by the dominating set contains a perfect matching. In this paper, we show that no minimum degree is sufficient to guarantee the existence of a disjoint dominating set and a paired-dominating set. However, we prove that the vertex set of every cubic graph can be partitioned into a dominating set and a paired-dominating set.     

Bounding the feedback vertex number of digraphs in terms of vertex degrees

The Turán bound (Turán (1941) [17]) is a famous result in graph theory, which relates the independence number of an undirected graph to its edge density. Also the Caro-Wei inequality (Caro (1979) [4] and Wei (1981) [18]), which gives a more refined bound in terms of the vertex degree sequence of a graph, might be regarded today as a classical result. We show how these statements can be generalized to directed graphs, thus yielding a bound on directed feedback vertex number in terms of vertex out-degrees and in terms of average out-degree, respectively.     

Antimagic labeling of generalized pyramid graphs

An antimagic labeling of a graph withq edges is a bijection from the set of edges to the set of positive integers{1,2,...,q}such that all vertex weights are pairwise distinct,where the vertex weight of a vertex is the sum of the labels of all edges incident with that vertex.A graph is antimagic if it has an antimagic labeling.In this paper,we provide antimagic labelings for a family of generalized pyramid graphs.     

全矩阵环上理想包含图的自同构群

设R是一个环,其上的理想包含图,记为Γ_I(R),是一个有向图,它以R的非平凡左理想为顶点,从R的左理想I_1到I_2有一条有向边当且仅当I_1真包含于I_2.环R上的理想关系图,记为Γ_i(R),也是一个有向图,它以R为顶点集,从R中元素A到B有一条有向边当且仅当A生成的左理想真包含于B生成的左理想.设F_q为有限域,其上n阶全矩阵环记为M_n(F_q),本文刻画了环M_n(F_q)上的理想包含图以及理想关系图的任意自同构.     

On the rank spread of graphs

For a simple graph G?=?(𝒱, ?) with vertex-set 𝒱?=?{1,?…?,?n}, let 𝒮(G) be the set of all real symmetric n-by-n matrices whose graph is G. We present terminology linking established as well as new results related to the minimum rank problem, with spectral properties in graph theory. The minimum rank mr(G) of G is the smallest possible rank over all matrices in 𝒮(G). The rank spread r _v (G) of G at a vertex v, defined as mr(G)???mr(G???v), can take values ??∈?{0,?1,?2}. In general, distinct vertices in a graph may assume any of the three values. For ??=?0 or 1, there exist graphs with uniform r _v (G) (equal to the same integer at each vertex v). We show that only for ??=?0, will a single matrix A in 𝒮(G) determine when a graph has uniform rank spread. Moreover, a graph G, with vertices of rank spread zero or one only, is a λ-core graph for a λ-optimal matrix A in 𝒮(G). We also develop sufficient conditions for a vertex of rank spread zero or two and a necessary condition for a vertex of rank spread two.     

上连通和超连通的三次Bi-Cayley图

Let G be a finite group and let S(possibly, contains the identity element) be a subset of G. The Bi-Cayley graph BC(G, S) is a bipartite graph with vertex set G×{0, 1} and edge set {(g, 0) (sg, 1) : g∈G, s ∈ S}. A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if every minimum vertex cut creates two components, one of which is an isolated vertex. In this paper, super-connected and/or hyper-connected cubic Bi-Cayley graphs are characterized.     

The primitive ideals of the Cuntz–Krieger algebra of a row-finite higher-rank graph with no sources

We catalogue the primitive ideals of the Cuntz–Krieger algebra of a row-finite higher-rank graph with no sources. Each maximal tail in the vertex set has an abelian periodicity group of finite rank at most that of the graph; the primitive ideals in the Cuntz–Krieger algebra are indexed by pairs consisting of a maximal tail and a character of its periodicity group. The Cuntz–Krieger algebra is primitive if and only if the whole vertex set is a maximal tail and the graph is aperiodic.     

笛卡尔乘积图里的最小k-路点覆盖

对于子集$S\subseteq V(G)$,如果图$G$里的每一条$k$路都至少包含$S$中的一个点,那么我们称集合$S$是图$G$的一个$k$-路点覆盖.很明显,这个子集并不唯一.我们称最小的$k$-路点覆盖的基数为$k$-路点覆盖数, 记作$\psi_k(G)$.本文给出了一些笛卡尔乘积图上$\psi_k(G)$值的上界或下界.     

Compact Compatible Topologies for Posets and Graphs

A topology on the vertex set of a comparability graph G is said to be compatible (respectively, weakly compatible) with G if each induced subgraph (respectively, each finite induced subgraph) is topologically connected if and only it it is graph-connected; a weakly compatible topology on the vertex set of a graph completely determines the graph structure. We consider here the problem of deciding whether or not a comparability graph has a compact compatible or weakly compatible topology and in the case of graphs with small cycles, hence in the case of trees, we give a characterization.     

The disjunctive domination number of a graph

Abstract

For a positive integer b, we define a set S of vertices in a graph G as a b-disjunctive dominating set if every vertex not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it. The b-disjunctive domination number is the minimum cardinality of such a set. This concept is motivated by the concepts of distance domination and exponential domination. In this paper, we start with some simple results, then establish bounds on the parameter especially for regular graphs and claw-free graphs. We also show that determining the parameter is NP-complete, and provide a linear-time algorithm for trees.     

Containment relations in split graphs

A graph containment problem is to decide whether one graph can be modified into some other graph by using a number of specified graph operations. We consider edge deletions, edge contractions, vertex deletions and vertex dissolutions as possible graph operations permitted. By allowing any combination of these four operations we capture the following ten problems: testing on (induced) minors, (induced) topological minors, (induced) subgraphs, (induced) spanning subgraphs, dissolutions and contractions. A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. Our results combined with existing results settle the parameterized complexity of all ten problems for split graphs.     

Applying local search to the feedback vertex set problem

The feedback vertex set problem (FVSP) consists in making a given directed graph acyclic by removing as few vertices as possible. In spite of the importance of this NP-hard problem, no local search approach had been proposed so far for tackling it. Building on a property of acyclic graphs, we suggest in this paper a new representation of the solutions of the FVSP (feedback sets). Thanks to this solution representation, we are able to design a local transformation (equivalent to a neighborhood) that changes a feedback set into a new one. Based on this neighborhood, we have developed a simulated annealing algorithm for the FVSP. Our experiments show that our algorithm outperforms the best existing heuristic, namely the greedy adaptive search procedure by Pardalos et al.     

Total restrained bondage in graphs

A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V (G) S is also adjacent to a vertex in V (G) S. The total restrained domination number of G is the minimum cardinality of a total restrained dominating set of G. In this paper we initiate the study of total restrained bondage in graphs. The total restrained bondage number in a graph G with no isolated vertex, is the minimum cardinality of a subset of edges E such that G E has no isolated vertex and the total restrained domination number of G E is greater than the total restrained domination number of G. We obtain several properties, exact values and bounds for the total restrained bondage number of a graph.     

Domination-balanced graphs

A set D of vertices in a graph is said to be a dominating set if every vertex not in D is adjacent to some vertex in D. The domination number β(G) of a graph G is the size of a smallest dominating set. G is called domination balanced if its vertex set can be partitioned into β(G) subsets so that each subset is a smallest dominating set of the complement G of G. The purpose of this paper is to characterize these graphs.